All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Up to 35 (Posted on 2004-11-14) Difficulty: 3 of 5
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?

See The Solution Submitted by Brian Smith    
Rating: 3.5000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Hints/Tips Am I seeing all the possibilities? (solution, if I am) | Comment 1 of 5

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

Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information