IMO 1994 SL N1

Origin: BUL | Category: Number Theory

Problem

M is a subset of {1, 2, 3, . . ., 15} such that the product of any three distinct elements of M is not a square. Determine the maximum number of elements in M.

Solution

Since for each of the subsets {1, 4, 9}, {2, 6, 12}, {3, 5, 15} and {7, 8, 14} the product of its elements is a square and these subsets are disjoint, we have |M| \leq11. Suppose that |M| = 11. Then 10 \inM and none of the disjoint subsets {1, 4, 9}, {2, 5}, {6, 15}, {7, 8, 14} is a subset of M. Consequently {3, 12} \subsetM, so none of {1}, {4}, {9}, {2, 6}, {5, 15}, and {7, 8, 14} is a subset of M: thus |M| \leq9, a contradiction. It follows that |M| \leq10, and this number is attained in the case M = {1, 4, 5, 6, 7, 10, 11, 12, 13, 14}.