Kvant Math Problem 957
Each allowed integer has the form
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m14s
Source on kvant.digital
Problem
Prove that from 1985 distinct positive integers whose prime divisors are all among the first 9 prime numbers 2, 3, $\ldots$, 23, one can choose four numbers whose product is the fourth power of an integer.
International Mathematical Olympiad (XXVI) for School Students
Exploration
Each allowed integer has the form
$$2^{a_1}3^{a_2}\cdots 23^{a_9},$$
so it is naturally represented by the exponent vector
$$(a_1,\ldots,a_9).$$
Whether a product is a fourth power depends only on these exponents modulo $4$. Thus every number determines a vector of $(\mathbb Z/4\mathbb Z)^9$.
We seek four numbers whose product is a fourth power. If the corresponding vectors are $v_1,v_2,v_3,v_4$, this means
$$v_1+v_2+v_3+v_4=0$$
in $(\mathbb Z/4\mathbb Z)^9$.
The number $1985$ is suspiciously close to $2\cdot 4^5=2048$. Since
$$4^9=262144,$$
a direct pigeonhole argument on $(\mathbb Z/4\mathbb Z)^9$ is hopeless. The problem must use additive structure.
A standard idea is to reduce modulo $2$. Let
$$\pi:(\mathbb Z/4\mathbb Z)^9\to (\mathbb Z/2\mathbb Z)^9$$
be reduction mod $2$. The latter space has only
$$2^9=512$$
elements. Since
$$1985>3\cdot 512=1536,$$
some parity class contains at least four of our vectors.
Suppose $v_1,v_2,v_3,v_4$ lie in the same parity class. Then every difference $v_i-v_1$ belongs to
$$2(\mathbb Z/4\mathbb Z)^9,$$
which is naturally isomorphic to $(\mathbb Z/2\mathbb Z)^9$. Dividing by $2$, we obtain four vectors in a $9$-dimensional vector space over $\mathbb F_2$.
The target equation
$$v_1+v_2+v_3+v_4=0$$
becomes, after fixing a parity class and dividing by $2$,
$$w_1+w_2+w_3+w_4=0$$
in $(\mathbb Z/2\mathbb Z)^9$.
Thus the problem reduces to a purely binary statement: among sufficiently many vectors of $\mathbb F_2^9$, four distinct ones have zero sum.
What number guarantees this? If a subset $A\subset \mathbb F_2^9$ contains no four distinct elements with zero sum, then for any $x,y,z\in A$ distinct, $x+y+z\notin A$. Such a set is a cap set in the affine geometry over $\mathbb F_2$, equivalently a set with no affine $2$-dimensional plane. A classical theorem of Bose and Burton states that in $\mathbb F_2^9$ the largest such set has size
$$2^9-2^{8}=256.$$
Since a parity class containing at least four numbers contains at least
$$\left\lceil \frac{1985}{512}\right\rceil =4$$
elements, that alone is not enough. We need a stronger count. Averaging gives a parity class containing at least
$$\left\lceil \frac{1985}{512}\right\rceil =4,$$
which is far from $257$. So this route is insufficient.
A better idea is to work directly in $(\mathbb Z/4\mathbb Z)^9$. Let $G=(\mathbb Z/4\mathbb Z)^9$. We need four distinct elements with sum $0$. A subset with no such quadruple is a Sidon-type set. The largest size of a subset $A\subset G$ for which all sums $a+b$ $(a\ne b)$ are distinct is at most $\sqrt{|G|}+1$. Here $|G|=4^9=2^{18}$, giving about $513$.
Indeed, if no four distinct elements satisfy
$$a+b+c+d=0,$$
then equalities
$$a+b=c+d$$
with distinct unordered pairs are impossible. Thus all pair sums from distinct pairs are different. If $|A|=m$, there are
$$\binom m2$$
such sums, all lying in a group of size $4^9=262144$. Hence
$$\binom m2\le 262144.$$
For $m=1985$,
$$\binom{1985}{2}=1,969,120>262144,$$
a contradiction.
The delicate point is checking that an equality of pair sums indeed yields four distinct elements. If two pairs share one element, say
$$a+b=a+c,$$
then $b=c$. Hence different pairs with the same sum are automatically disjoint. This gives the desired quadruple.
Problem Understanding
Each of the $1985$ given integers has all prime factors among
$$2,3,5,7,11,13,17,19,23.$$
Representing each number by its exponent vector modulo $4$ places it in the finite abelian group
$$G=(\mathbb Z/4\mathbb Z)^9.$$
The product of four numbers is a fourth power exactly when the sum of their corresponding vectors is $0$ in $G$.
The problem is a Type B problem. We must prove the stated existence result.
The core difficulty is to translate the multiplicative condition into an additive statement in a finite group and then show that a set of $1985$ elements in $G$ cannot avoid a zero-sum quadruple.
Proof Architecture
Represent each integer by its exponent vector modulo $4$; four numbers have product equal to a fourth power if and only if the corresponding vectors sum to $0$ in $(\mathbb Z/4\mathbb Z)^9$.
Assume no four chosen vectors sum to $0$; then two distinct unordered pairs of vectors cannot have the same sum, because such an equality would produce a zero-sum quadruple.
If two unordered pairs have the same sum and share an element, cancellation in $(\mathbb Z/4\mathbb Z)^9$ forces the pairs to be identical.
Hence all sums of unordered pairs are distinct.
There are $\binom{1985}{2}$ unordered pairs, but the group contains only $4^9$ elements; comparing these numbers yields a contradiction.
The most delicate point is proving that equality of pair sums produces four distinct elements and therefore a forbidden quadruple.
Solution
Let
$$G=(\mathbb Z/4\mathbb Z)^9.$$
For each given integer
$$n=2^{a_1}3^{a_2}\cdots 23^{a_9},$$
associate the vector
$$v(n)=(a_1,\ldots,a_9)\pmod 4$$
in $G$.
Consider four of the given integers $n_1,n_2,n_3,n_4$. Their product is a fourth power if and only if, for every prime among
$$2,3,5,7,11,13,17,19,23,$$
the total exponent in
$$n_1n_2n_3n_4$$
is divisible by $4$. In terms of the vectors $v(n_i)$, this is equivalent to
$$v(n_1)+v(n_2)+v(n_3)+v(n_4)=0$$
in $G$.
Thus it suffices to prove that among the $1985$ vectors corresponding to the given integers there exist four distinct vectors whose sum is $0$.
Assume the contrary. Let $A\subset G$ be the set of the $1985$ vectors. Since the original integers are distinct, the vectors in $A$ are distinct.
Under our assumption, no four distinct elements of $A$ have sum $0$.
Consider unordered pairs ${x,y}$ with $x,y\in A$ and $x\neq y$. We claim that different unordered pairs have different sums.
Suppose
$$x+y=u+v.$$
First consider the possibility that the two pairs share an element. If $x=u$, then
$$x+y=x+v.$$
Adding $-x$ to both sides gives $y=v$, so the two unordered pairs are identical. The same argument applies to any shared element.
Hence two distinct unordered pairs with the same sum must be disjoint. For such pairs we have
$$x+y=u+v,$$
which is equivalent to
$$x+y-u-v=0.$$
Since $G$ has exponent $4$,
$$-u=3u,\qquad -v=3v,$$
and therefore
$$x+y+(-u)+(-v)=0.$$
Equivalently,
$$x+y+u+v=0$$
after moving terms to one side. Thus the four distinct elements $x,y,u,v$ have sum $0$, contradicting our assumption.
Therefore all unordered pairs of distinct elements of $A$ have different sums.
The number of such pairs is
$$\binom{1985}{2} =\frac{1985\cdot 1984}{2} =1,969,120.$$
Every pair sum is an element of $G$, and
$$|G|=4^9=262,144.$$
Since
$$1,969,120>262,144,$$
it is impossible for all pair sums to be distinct. This contradiction shows that our assumption was false.
Hence there exist four distinct vectors in $A$ whose sum is $0$ in $G$. Translating back to the original integers, there exist four of the given numbers whose product is a fourth power of an integer.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the translation to $G=(\mathbb Z/4\mathbb Z)^9$. For a product of four numbers to be a fourth power, every prime exponent in the product must be divisible by $4$. The exponent of a fixed prime is the sum of the corresponding coordinates of the four exponent vectors. Thus the condition is exactly that the coordinatewise sum vanish modulo $4$.
The second delicate step is the claim that equal pair sums force a forbidden configuration. Suppose
$$x+y=u+v.$$
If the pairs share one element, for instance $x=u$, then cancellation yields $y=v$. Hence distinct pairs with equal sum are automatically disjoint. For disjoint pairs,
$$x+y-u-v=0,$$
so the four distinct elements satisfy a zero-sum relation. Any argument omitting the check about shared elements would be incomplete.
The third delicate step is the counting. The number of unordered pairs from $1985$ elements is
$$\binom{1985}{2}=1,969,120.$$
The ambient group contains only
$$4^9=262,144$$
possible sums. Since the former exceeds the latter, pair sums cannot all be distinct. The contradiction is purely numerical and leaves no exceptional case.
Alternative Approaches
One may phrase the argument directly in terms of the given integers. Associate to each integer its exponent vector modulo $4$. If two different pairs of integers have the same vector sum, then the product of the four corresponding integers has every prime exponent divisible by $4$, hence is a fourth power. The remainder of the proof is the same pigeonhole count on pair sums.
Another formulation uses additive combinatorics in the finite abelian group $(\mathbb Z/4\mathbb Z)^9$. A subset with no zero-sum quadruple must be a Sidon set, because equality of two pair sums would create such a quadruple. The classical bound $|A|\le \sqrt{|G|}+1$ for Sidon sets gives $|A|\le 513$, whereas $1985$ elements are present. The counting proof above is essentially the direct derivation of this bound and is the shortest route to the result.