IMO 1985 Problem 4

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 9m00s

Problem

Given a set $M$ of $1985$ distinct positive integers, none of which has a prime divisor greater than $23$, prove that $M$ contains a subset of $4$ elements whose product is the $4$th power of an integer.

Exploration

The original approach fails because it tries to force a 4-term zero sum inside a single parity class, where no additive structure is guaranteed. A correct strategy must exploit a setting where the number of available combinatorial objects exceeds the number of possible residue values in a way that produces an unavoidable collision with strong structural consequences.

Each integer corresponds to a vector in $\mathbb{Z}_4^9$. The target condition is that four vectors $a,b,c,d$ satisfy

$a+b+c+d \equiv 0 \pmod 4,$

coordinatewise.

Testing small analogues clarifies what kind of mechanism is plausible. In $\mathbb{Z}_4^1$, any sufficiently large multiset does not force a zero-sum quadruple among arbitrary elements, but collisions among pair sums become unavoidable much earlier than collisions among individual elements. For instance, among many integers modulo $4$, repeated values of $x+y \bmod 4$ appear quickly, while forcing a 4-term cancellation directly is harder.

This suggests shifting from single elements to pair-sums. If two disjoint pairs satisfy

$a+b \equiv c+d \pmod 4,$

then rearranging gives a valid 4-term zero sum.

The key issue is whether disjointness can be guaranteed when two pairs share the same sum vector in $\mathbb{Z}_4^9$. This must be checked carefully, since overlap could otherwise destroy the construction.

Problem Understanding

Each integer in $M$ has the form

$n=\prod_{p\in{2,3,5,7,11,13,17,19,23}} p^{e_p(n)}.$

We associate to $n$ its exponent vector

$v(n) \in \mathbb{Z}_4^9,$

where coordinates are taken modulo $4$.

A subset ${a,b,c,d}$ satisfies that $abcd$ is a fourth power if and only if

$v(a)+v(b)+v(c)+v(d) \equiv 0 \pmod 4.$

Thus the task is to find four vectors in $\mathbb{Z}_4^9$ with zero sum.

Key Observations

The set $\mathbb{Z}_4^9$ has $4^9=262144$ elements.

The number of unordered pairs from a set of size $1985$ equals

$\binom{1985}{2} = 1,969,120,$

which is strictly larger than $4^9$.

This disparity forces two distinct pairs to share the same sum in $\mathbb{Z}_4^9$ under the map

$(a,b)\mapsto v(a)+v(b).$

If such pairs are disjoint, their equality of sums immediately produces a zero-sum quadruple.

The only remaining structural issue is whether non-disjoint pairs can create false collisions; this must be excluded explicitly.

Solution

For each unordered pair ${a,b}\subset M$, define its pair-sum vector

$s(a,b)=v(a)+v(b)\in \mathbb{Z}_4^9.$

There are $\binom{1985}{2}$ such pairs and only $4^9$ possible values of $s(a,b)$. Since

$\binom{1985}{2} > 4^9,$

there exist distinct pairs ${a,b}$ and ${c,d}$ such that

$v(a)+v(b) \equiv v(c)+v(d) \pmod 4.$

It remains to show that these two pairs can be taken to be disjoint.

If the pairs share exactly one element, say $a=c$, then

$v(a)+v(b)\equiv v(a)+v(d)\pmod 4,$

which implies $v(b)\equiv v(d)\pmod 4$, hence $b=d$ since elements of $M$ are distinct. This contradicts that the pairs are distinct.

If the pairs share both elements, they are identical. Hence two distinct pairs with equal sum must be disjoint.

Therefore we obtain four distinct elements $a,b,c,d$ such that

$v(a)+v(b)\equiv v(c)+v(d)\pmod 4.$

Rearranging gives

$v(a)+v(b)+v(c)+v(d)\equiv 0 \pmod 4,$

coordinatewise.

Thus the product $abcd$ is a perfect fourth power.

This completes the proof. ∎

Verification of Key Steps

The encoding into exponent vectors is correct since multiplication corresponds to addition of exponent vectors and fourth powers correspond to divisibility by $4$ in each coordinate.

The counting step is valid because $\binom{1985}{2}$ exceeds $4^9$, guaranteeing a collision among pair-sums by the pigeonhole principle.

The disjointness argument is structurally forced: any overlap between two pairs would reduce the equality of pair-sums to equality of individual elements, contradicting distinctness. This ensures that the collision produces four distinct indices.

The final rearrangement from equality of pair-sums to a zero total sum is a direct algebraic identity in $\mathbb{Z}_4^9$.

Alternative Approaches

A different method replaces pair-sums with group-theoretic zero-sum constants in finite abelian $2$-groups and $4$-groups, using the Davenport constant of $\mathbb{Z}_4^9$. That approach avoids explicit counting of pairs but requires deeper structural results.

Another approach iterates mod $2$ and mod $4$ filtrations to build a controlled lifting from $\mathbb{Z}_2^9$ to $\mathbb{Z}_4^9$, but it ultimately reconstructs a mechanism equivalent to the pair-sum collision argument used here.