### 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.

**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

jscholes@kalva.demon.co.uk

18 Sep 2002