Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
What have you tried? –  Jonas Meyer Jul 6 '12 at 3:38
    
Sounds like the pigeon hole principle will come into play? –  Jyrki Lahtonen Jul 6 '12 at 4:07
add comment

1 Answer

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}. $$
share|improve this answer
    
You mean $131\choose 4$? –  Jonas Meyer Jul 6 '12 at 4:17
    
@Jonas: No. Counting pairs. Two pairs make a quartet. –  Jyrki Lahtonen Jul 6 '12 at 4:19
    
Thank you. My mistake. –  Jonas Meyer Jul 6 '12 at 4:20
    
Initially I though that there is a little bit of slack in the number 131. I was wrong :-) –  Jyrki Lahtonen Jul 6 '12 at 4:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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