From any list of $131$ positive integers with prime factor at most $41$, $4$ can always be chosen such that their product is a perfect square

Question

Author's note:I don't want the whole answer,but a guide as to how I should think about this problem.

BdMO 2010

In a set of $131$ natural numbers, no number has a prime factor greater than 42. Prove that it is possible to choose four numbers from this set such that their product is a perfect square.

The above question obviously has "PIGEONHOLE" written all over its face.However,finding the pigeons and holes is the hard part.The first thing to realize is that the number of primes is 13.We can write any number of our list using those primes.Now,since we only care about whether the exponents of the primes are even or odd,there are a total of $2^{13}$ types of integers.I have done a lot more computation but I am unable to see how this is leading us to pigeonholing(okay,I will admit that I should be a little more open-minded but I am certain that this uses pigeonholing).Also,the only way four integers can add up to an even number is if there are an even number of integers of the same parity.In that case,there are a total of $8$ cases for every quadruple of exponents(counting permutations).

A hint will be appreciated.Also,any mention of how you came up with your own solution will be very much appreciated.

EDIT: I have just found this

EDIT: I may have taken a step towards a solution.We can rewrite each of the integers as $x^2m$ where $m$ is squarefree.The number of possible $m$'s is $2^13$ .Now,if we show that there is another integer with the same $x$ part,and argue the same way with another pair of integers,and then multiply them together,our solution will be complete.However,I don't think that the claim is at all true.

Answer 1

There are $\binom{131}{2}=8515>2^{13}$ possible ways to choose a pair $(x,y)$. So we must have at least two different pairs $(x_1,y_1),(x_2,y_2)$ such that their squarefree product is equal. If those pairs do not share an element, we are done. If not, suppose that $x_1=x_2$. So $y_1y_2$ is a perfect square.

Remove $y_1y_2$ from the list. There are $\binom{129}{2}=8256>2^{13}$ possible ways to choose a pair $(w,z)$ now. In the same way, we have two different pairs $(w_1,z_1),(w_2,z_2)$ such that their squarefree product is equal. If those pairs do not share an element, we are done. If not, supposing that $w_1=w_2$, we now have that $z_1z_2$ is a perfect square.

So either $x_1y_1x_2y_2$ or $y_1y_2z_1z_2$ are perfect squares,

Answer 2

HINT - though I haven't followed through a solution ...

Finding four numbers all at once could be hard. Sometimes divide and conquer goes along with pigeonhole - using pigeonhole to find (disjoint) pairs which give the right parity on some fixed subset of the prime factors, and then using it again to find two pairs which match on the rest - but whether that works depends on whether you can find the right number of pairs for the second stage.