Square-free
Probability
Level
4
What is the maximum number of elements that can be chosen from such that no two chosen numbers have a product that is a perfect square?
The answer is 16.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
If you choose all the primes, you won't have any square pairs. If you add all the composites of the form p x q with p and q distinct primes you are still safe. Then you can add one prime squared to the mix and still avoid square pairs.
It seems clear that this is optimal in this case (and can be generalized for large enough sets), but I'm not sure of a fast way to prove it.
You end up with 9 + 6 + 1 = 16.