Kvant Math Problem 150
For $n=1$ the statement is immediate.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m57s
Source on kvant.digital
Problem
From the numbers 1, 2, $\ldots$, $k$ all possible $(a_1,a_2,\ldots,a_n)$-tuples of length $n$ are formed (it is easy to see that there are $k^n$ of them). Two subsets $P$ and $Q$ of such tuples are chosen (the same tuple may belong to both $P$ and $Q$). It is known that if we take an arbitrary tuple $(p_1,p_2,\ldots,p_n)$ from $P$ and an arbitrary tuple $(q_1,q_2,\ldots,q_n)$ from $Q$, then they coincide in at least one position (that is, $p_i=q_i$ for some $i$). Then either $P$ or $Q$ contains no more than $k^{n-1}$ tuples.
Prove this statement
- for $k=2$ and arbitrary $n$;
- for $n=1$, 2, 3 and arbitrary $k\ge2$;
- for arbitrary $k\ge2$ and $n\ge1$.
Try to find other restrictions on the number of elements in the subsets $P$ and $Q$ connected by such a condition.
V. B. Alekseev
Exploration
For $n=1$ the statement is immediate. If $P,Q\subset{1,\dots,k}$ and every $p\in P$ equals every $q\in Q$, then all elements of $P\cup Q$ are the same number, hence one of the sets has at most one element.
For $k=2$ there is a particularly simple reformulation. Associate to each binary vector $x=(x_1,\dots,x_n)$ its complement
$$\bar x=(3-x_1,\dots,3-x_n).$$
Two binary vectors fail to coincide in every position precisely when they are complements. Thus the condition says that no pair $(x,\bar x)$ may occur with $x\in P$ and $\bar x\in Q$. Since the $2^n$ binary vectors split into $2^{n-1}$ complementary pairs, each pair contributes at most one element to $P\cup \bar Q$. Hence
$$|P|+|Q|\le 2^n.$$
From this one immediately gets $\min(|P|,|Q|)\le 2^{n-1}$.
For general $k$ the complement argument disappears. A first guess is to seek an injective map from $Q$ into the complement of $P$, but the natural candidate,
$$q\mapsto (q_1+1,\dots,q_n+1)\pmod k,$$
fails because changing all coordinates does not guarantee avoidance of all points of $P$.
The condition is that $P$ and $Q$ are cross-intersecting in the Hamming scheme: every pair agrees somewhere. The opposite relation is complete disagreement in every coordinate. The number of vectors completely disagreeing with a fixed vector equals $(k-1)^n$.
The key step is likely to be the averaging argument. For each vector $x=(x_1,\dots,x_n)$ and each shift $a=(a_1,\dots,a_n)\in{0,\dots,k-1}^n$, define
$$x+a=(x_1+a_1,\dots,x_n+a_n)\pmod k.$$
If $P+a$ intersects $Q$, then there exist $p\in P$, $q\in Q$ with $p+a=q$. Coordinatewise this means
$$a_i=q_i-p_i.$$
If all coordinates of $a$ are nonzero modulo $k$, then $p_i\ne q_i$ for every $i$, contradicting the hypothesis. Hence every admissible shift $a$ has at least one zero coordinate.
Now count. There are $k^n$ shifts altogether. Exactly $(k-1)^n$ of them have no zero coordinates, so at most
$$k^n-(k-1)^n$$
shifts can satisfy $(P+a)\cap Q\ne\varnothing$.
On the other hand, for every pair $(p,q)\in P\times Q$ there is a unique shift $a=q-p$. Thus the number of shifts with nonempty intersection, counted with multiplicity, equals $|P||Q|$. Since for a fixed shift the intersection size is at most $k^{n-1}$? That direction seems weak.
A better formulation is
$$\sum_a |(P+a)\cap Q|=|P||Q|.$$
The average value of $|(P+a)\cap Q|$ over all shifts equals
$$\frac{|P||Q|}{k^n}.$$
Since only shifts with at least one zero coordinate contribute,
$$|P||Q|\le k^n\bigl(k^n-(k-1)^n\bigr)/k^n.$$
This gives
$$|P||Q|\le k^n-(k-1)^n.$$
For $k=2$ this becomes $|P||Q|\le 2^n-1$, which is weaker than desired but still enough to imply one set has size at most $2^{n-1}$ because otherwise the product would exceed $2^{2n-2}$.
Yet for large $k$ this product bound is not enough. For example,
$$k^n-(k-1)^n\sim nk^{n-1},$$
while if both sets exceeded $k^{n-1}$ the product would exceed $k^{2n-2}$, which is much larger when $n\ge3$.
The correct inequality should be
$$|P||Q|\le k^{2n-1},$$
which immediately gives the theorem. How to obtain it? The previous averaging suggests considering only shifts with at least one zero coordinate. There are exactly
$$k^n-(k-1)^n$$
such shifts, and this quantity is at most $nk^{n-1}$, not $k^{n-1}$. This still does not suffice directly.
Perhaps one should induct on $n$. Partition $P$ and $Q$ by the first coordinate:
$$P_i={(i,x_2,\dots,x_n)\in P}, \qquad Q_i={(i,x_2,\dots,x_n)\in Q}.$$
If $p\in P_i$ and $q\in Q_j$ with $i\ne j$, then their tails must intersect somewhere among the last $n-1$ coordinates. Thus the projected sets
$$P_i',Q_j'$$
are cross-intersecting in dimension $n-1$.
Assume every $|P_i|>k^{n-2}$ and every $|Q_j|>k^{n-2}$. Then by induction each pair with $i\ne j$ is impossible. Hence at most one $P_i$ and at most one $Q_j$ are nonempty, and their indices must coincide. Then
$$|P|,|Q|\le k^{n-1}.$$
This line seems promising but requires careful handling because some classes may be small.
A cleaner approach uses graph theory. Let $G$ be the graph on $k^n$ tuples where adjacency means disagreement in every coordinate. Then $G$ is regular of degree $(k-1)^n$. The condition says there are no edges between $P$ and $Q$. The graph is vertex-transitive. The classical No-Homomorphism lemma or Hoffman bound might yield
$$|P||Q|\le k^{2n-2}.$$
But an elementary proof is preferable.
There is a known theorem of Chung-Graham-Frankl-Shearer: for cross-intersecting families in $[k]^n$ one has $|P||Q|\le k^{2n-2}$. Equality occurs for dictatorships such as all vectors with first coordinate $1$.
The induction can prove exactly this stronger statement. Let
$$p_i=|P_i|,\qquad q_i=|Q_i|.$$
For $i\ne j$, induction gives
$$p_iq_j\le k^{2n-4}.$$
Summing cleverly may work.
Suppose $p_r=\max p_i$. Then
$$p_r\ge |P|/k.$$
If $|P|>k^{n-1}$, then $p_r>k^{n-2}$.
For every $j\ne r$, the families $P_r'$ and $Q_j'$ are cross-intersecting in dimension $n-1$. Since $|P_r'|>k^{n-2}$, induction forces
$$|Q_j'|\le k^{n-2}.$$
Hence
$$|Q|\le q_r+(k-1)k^{n-2}.$$
If also $|Q|>k^{n-1}$, then
$$q_r>k^{n-2}.$$
Applying the same argument to $P_j'$ versus $Q_r'$ gives $p_j\le k^{n-2}$ for all $j\ne r$. Therefore
$$|P|\le p_r+(k-1)k^{n-2}.$$
But now for $i\ne r$, $j\ne r$, both $p_i,q_j\le k^{n-2}$.
Need contradiction. If there were some $j\ne r$ with $q_j>0$, then by induction applied to $P_r',Q_j'$ and the fact $|P_r'|>k^{n-2}$, we get $q_j\le k^{n-2}$ only, not contradiction.
Maybe the induction hypothesis should be the stronger product inequality
$$|P||Q|\le k^{2n-2}.$$
Then the theorem follows immediately.
Indeed, fixing $r$ with maximal $p_r$, for every $j\ne r$:
$$p_rq_j\le k^{2n-4}.$$
Thus
$$q_j\le \frac{k^{2n-4}}{p_r}.$$
Summing,
$$|Q|=\sum q_j\le q_r+\frac{(k-1)k^{2n-4}}{p_r}.$$
Similarly,
$$p_iq_r\le k^{2n-4}\quad(i\ne r),$$
so
$$|P|\le p_r+\frac{(k-1)k^{2n-4}}{q_r}.$$
Need derive product bound. By AM-GM,
$$|P||Q| \le \left(p_r+\frac{A}{q_r}\right)\left(q_r+\frac{A}{p_r}\right) = p_rq_r+2A+\frac{A^2}{p_rq_r},$$
where $A=(k-1)k^{2n-4}$.
This expression is maximized? Let $t=p_rq_r$. Then
$$f(t)=t+2A+A^2/t.$$
Need show $f(t)\le k^{2n-2}$. Since by trivial bounds $t\le k^{2n-2}$ maybe. Compute at $t=A$ gives $4A=4(k-1)k^{2n-4}$, not enough.
Need another ingredient. Perhaps $P_r',Q_r'$ themselves are cross-intersecting, so
$$p_rq_r\le k^{2n-4}.$$
Then
$$|P||Q|\le (kA/p_r)(kA/q_r)=k^2A^2/(p_rq_r)\le k^2A=k^2(k-1)k^{2n-4}= (k-1)k^{2n-2},$$
too weak.
Need sharper manipulation:
$$|P|\le p_r+(k-1)\frac{B}{q_r}, \quad |Q|\le q_r+(k-1)\frac{B}{p_r},$$
with $B=k^{2n-4}$ and $p_rq_r\le B$.
Then
$$|P||Q| \le \left(p_r+\frac{(k-1)B}{q_r}\right)\left(q_r+\frac{(k-1)B}{p_r}\right)$$
$$= k(p_rq_r)+(k-1)^2\frac{B^2}{p_rq_r}.$$
Since $p_rq_r\le B$, letting $t=p_rq_r$,
$$f(t)=kt+(k-1)^2B^2/t.$$
For $0<t\le B$,
$$f'(t)=k-(k-1)^2B^2/t^2.$$
Maximum on interval occurs at endpoint. At $t=B$,
$$f(B)=kB+(k-1)^2B=(k^2-k+1?)$$
Compute:
$$k+(k-1)^2=k^2-k+1.$$
Then
$$f(B)=(k^2-k+1)k^{2n-4}<k^{2n-2}$$
because
$$k^2-(k^2-k+1)=k-1>0.$$
Good. Enough.
Need concise rigorous writeup.