Pigeonhole Principle – Olympiad Question on Elementary Set Theory

contest-mathelementary-set-theorypigeonhole-principle

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.

Best Answer

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$.

Related Question