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.

Improve this question
$\endgroup$
  • $\begingroup$ Sounds like the pigeon hole principle will come into play? $\endgroup$ – Jyrki Lahtonen Jul 6 '12 at 4:07
2
$\begingroup$

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}. $$
Improve this answer
$\endgroup$
  • $\begingroup$ You mean $131\choose 4$? $\endgroup$ – Jonas Meyer Jul 6 '12 at 4:17
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.