35th IMO 1994 shortlist Problem N1 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.
Problem 791
Official 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 2n 2 , 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 2n 2 , 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 = 3 2 2 3 , 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 = 6 2 ), 4 (4·3·12 = 12 2 ), 9 (9·3·12 = 18 2 ), one of 2, 6 (2·6·3 = 6 2 ) and one of 5, 15 (3·5·15 = 15 2 ), 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 = 10 2 ) and at least one of 1, 4, 9 (1·4·9 = 6 2 ) and at least one of 7, 8, 14 (7·8·14 = 28 2 ). Finally, suppose we exclude 10. But we must also exclude one of 1, 4, 9 (product 6 2 ), one of 2, 6, 12 (product 12 2 ), one of 3, 5, 15 (product 15 2 ) and one of 7, 8, 14 (product 28 2 ). So there are at most 10 elements. 35th IMO shortlist 1994 © John Scholes [email protected] 18 Sep 2002