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.
$\begingroup$
$\endgroup$
-
$\begingroup$ Sounds like the pigeon hole principle will come into play? $\endgroup$ – Jyrki Lahtonen Jul 6 '12 at 4:07
$\begingroup$
$\endgroup$
Hints:
- There are 13 primes below 42.
- $\displaystyle{131\choose 2}>2^{13}$.
- Easier version.
- 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}. $$
answered Jul 6 '12 at 4:15
-
-
$\begingroup$ @Jonas: No. Counting pairs. Two pairs make a quartet. $\endgroup$ – Jyrki Lahtonen Jul 6 '12 at 4:19
-
$\begingroup$ Initially I though that there is a little bit of slack in the number 131. I was wrong :-) $\endgroup$ – Jyrki Lahtonen Jul 6 '12 at 4:31
