Olympiad question on Pigeonhole principle

Question

Given a set $M$ of $1985$ distinct positive integers, none of which has a prime divisor greater than $26$, prove that $M$ contains at least one subset of four distinct elements, whose product is the fourth power of an integer.

I couldn't even start.

Answer 1

It could be interesting to show the more general case, that is, if we know the prime divisors of all elements in $M$ are amongst $p_{1}, p_{2}, ..., p_{n}$, and $M$ has at least $2^{n} \cdot 3 + 1$ elements, then it contains at least one subset of four distinct elements whose product is a fourth power.

The trick is to assign each element $m$ in $M$ with an $n$-tuple $(x_{1}, x_{2}, ..., x_{n})$, where $x_{i}$ is an indicator variable equal to $0$ if the exponent of $p_{i}$ in $m$'s prime factorization is even, and $1$ otherwise.

As my teacher explained this problem, these tuples become our objects with which to consider the pigeonhole principle, and our boxes are the possible choices of $0$'s and $1$'s for each indicator. Then by the pigeonhole principle, we have that every subset of our $2^{n}+1$ elements of $M$ contains two (distinct) elements with the same object, or $n$-tuple, and consequently the product of these two elements is a square.

Our process consists of repeatedly removing these pairs, and replacing them with two of our remaining possible numbers. Since $M$ has at least $2^{n}\cdot 3 + 1$ elements, we can select at least $2^{n}+1$ pairs.

Now we must consider the $2^{n}+1$ numbers that are products of the two elements of each pair. We can repeat the same argument as above once again, to have four elements $a,b,c,d$ in $M$ where $\sqrt{ab}\sqrt{cd}$ is a perfect square. Then $abcd$ is a fourth power, and our result has been shown.

In your case, we have that $n=9$, as $1985 > 3 \cdot 2^{9} + 1 = 1537$.

Answer 2

There are $9$ primes less than $26$.

You can look at each integer $n$ as a binary $9$-tuple that gives you the value of each $\alpha_i$ $\bmod 2$ when writing $n$ as $2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}7^{\alpha_4}11^{\alpha_5}13^{\alpha_6}17^{\alpha_7}19^{\alpha_8}23^{\alpha_9}$.

Hence we have $1985$ such lists. We shall prove there are two of these lists so that when we add them all nine terms are multiples of $2$. This is clear, since $1985>512=2^9$ which is the total number of possible lists ther must be two that are equal. So we take those two equal lists, they represent numbers $a$ and $b$. We delete numbers $a$ and $b$ from the list and we place their product $ab$ in a separate list. We continue to do this until we have $511$ numbers in the first list.

When we finish doing this the new list will have $(1985-511)/2=737$ numbers. So we will have in the new list $737$ squares. All these numbers are of the $2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}7^{\alpha_4}11^{\alpha_5}13^{\alpha_6}17^{\alpha_7}19^{\alpha_8}23^{\alpha_9}$. And each $\alpha_i$ is even. Convert each of these numbers into a binary $9$-tuple where term $i$ is the congruence $\bmod 4$ of $\alpha_i$.

Since $737>512=2^9$ there are two numbers that give the same list. The product of these two numbers is therefore a fourth power This proof works for as little as $1537$ numbers, but the problem statement say $1985$ because this is problem $4$ (second easiest) of the imo $1985$