2
$\begingroup$

Let be given $131$ distinct natural numbers, each having prime divisors not exceeding $42$. how to Prove that one can choose four of them whose product is a perfect square.

  • 0
    Sounds like the pigeon hole principle will come into play?2012-07-06

1 Answers 1

2

Hints:

  1. There are 13 primes below 42.
  2. $\displaystyle{131\choose 2}>2^{13}$.
  3. Easier version.
  4. Out comes two pairs of numbers $(a,b), a\neq b,$ and $(c,d), c\neq d,$ such that $abcd$ is a square. If all four are distinct, we are done. If, say $b=d$, then $ac$ is also a square. Repeat without $a$ and $c$ using $ \displaystyle{129\choose2}>2^{13}. $
  • 0
    Initially I though that there is a little bit of slack in the number 131. I was wrong :-)2012-07-06