S is a set of N distinct positive integers such that no member of S has a prime factor greater than 35. Let P be the set of products of members of S taken 2 at a time. (For example, if x, y and z are members of S, then xy, xz and yz will be members of P.)
What is the smallest value of N for which it is certain that P contains a perfect square?
2^11+1 = 2049
My solution is below. Charlie offers a solution here.
Each member of S can be written as R^2*F, where F has no perfect square factors other than 1. A square in P arrives when two members of S have the same F value. Since there are 11 prime numbers less than 35, there are 2^11 possible F values. And by the pigeon hole principle, if there are 2^11+1 members in S, two must have the same F value which means their product is a perfect square.
Comments: (
You must be logged in to post comments.)
