Find the largest possible subset of {1, 2, ... , 15} such that the product of any three distinct elements of the subset is not a square.
Solution
{1, 4, 5, 6, 7, 10, 11, 12, 13, 14} shows that we can have a subset of 10 elements with the required property.
[This is a matter of tiresome verification. Suppose there is a set T of 3 elements with product a square. If 5 is in T, then 10 must be in T (because it is the only other element divisible by 5). Hence the third element must be 2n2, but there is no such element. So 5 is not in T. Hence 10 is not in T. Similarly, if 7 is in T, then 14 must be in T, but then there is no third element of the form 2n2, so neither 7 nor 14 can be in T. 11 cannot be in T because it is the only element divisible by 11. Similarly 13. If 6 or 12 is in T, then the other must be (because they are the only elements divisible by 3). But then 6·12 = 3223, so the third element must be divisible by an odd power of 2 and there are none such (except for 10 and 14, which have already been eliminated). So there are at most two candidates for T (1 and 4) which is not enough.]
If we include 10, 3 and 12 then we must exclude 1 (1·3·12 = 62), 4 (4·3·12 = 122), 9 (9·3·12 = 182), one of 2, 6 (2·6·3 = 62) and one of 5, 15 (3·5·15 = 152), so there are at most 10 elements. If we include 10, and exclude one or more of 3, 12, then we must also exclude at least one of 2, 5 (2·5·10 = 102) and at least one of 1, 4, 9 (1·4·9 = 62) and at least one of 7, 8, 14 (7·8·14 = 282).
Finally, suppose we exclude 10. But we must also exclude one of 1, 4, 9 (product 62), one of 2, 6, 12 (product 122), one of 3, 5, 15 (product 152) and one of 7, 8, 14 (product 282). So there are at most 10 elements.
© John Scholes
jscholes@kalva.demon.co.uk
18 Sep 2002