The set $L$ consists of 2003 integers , none of which has a prime divisor larger than $24$. Prove that $L$ has four elements , the product of which is equal to the fourth power of an integer.
Above question statement , can someone please explain in simple intuitive manner how pigeonhole principle is applied in the question and how can we prove that?
I remember seeing a problem like this in a book of math puzzles, maybe it was Coffeetime in Memphis by Bollobás? Anyways, I remember the solution.
First, we prove that there exist two numbers, the product of which is a perfect square. There are $9$ primes less than 24, call them $p_1,\dots,p_9$, so each integer can be written as $ p_1^{n_1}\dots p_{9}^{n_9}, $ where $n_i$ is a nonnegative integer for each $i\in \{1,\dots,9\}$. Let us make $512=2^9$ pigeonholes, each labeled by a sequence of length nine whose entries are either "even" or "odd." Put each of the $2003$ numbers into the pigeonhole which describes its sequence of multiplicities $(n_1,\dots,n_9)$. Since there are many more pigeons than holes, there exist two numbers $x_1$ and $y_1$ in the same hole. You can then check that $x_1y_1$ has all even multiplcities in its prime factorization, so $x_1y_1$ is a perfect square.
Ok, but how does this help us? The next step is to remove $x_1$ and $y_1$, and return our attention to the remaining $2001$ integers. Note that $2001$ is still much greater than $512$, so we can still find a pair $x_2$ and $y_2$ for which $x_2y_2$ is a perfect square. Do this over and over again, for a total of $513$ times, resulting in a list of pairs $$ (x_1,y_1),\dots,(x_{513},y_{513}) $$ whose products are all perfect squares. Finally, apply the the same argument to the list $$\sqrt{x_1y_1},\dots,\sqrt{x_{513}y_{513}}$$ to find two products whose product is a perfect square, say that they are $\sqrt{x_iy_i}$ and $\sqrt{x_jy_j}$. Since $\sqrt{x_iy_i}\cdot\sqrt{x_jy_j}$ is a perfect square, it follows $x_iy_ix_jy_j$ is a perfect fourth power.
We used the pigeonhole principle $514$ times, surely this is some kind of record!