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?

There are 11 primes under 35: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31.  Each of these primes can occur in set S.  Any product of two of these primes can also occur in set S. C(11,2) = 55. That's 66 members so far without being able to form a square from a product of two of them.  We can also throw in one square of one of the primes, say 2^2=4.  That makes 67 that can safely be put into set S.  That would mean 68 is the smallest value of n that would force some product of two members to be a perfect square.

But wait: can we safely put in all the products of three different primes? I think we can. There are C(11,3)=165 of those. And the same with all the products of 4, 5, etc primes, up to the product of all 11 primes.

That makes the safe total 1 + Sigma{i=1 to 11} C(11,i), with the 1 at the beginning for the solitary prime squared allowed.  Then the minimum to surely prevent this (assure a perfect square in the product set) is one higher: 2+ Sigma{i=1 to 11} C(11,i). The sum of the combinations is 11 + 55 + 165 + 330 + 462 + 462 + 330 + 165 + 55 + 11 + 1 = 2047.  The safe total is therefore 2048, and the number guaranteeing a square is 2049.

 

Edited on November 14, 2004, 11:41 am

Posted by Charlie on 2004-11-14 11:39:09