23rd Australian 2002 Problem A4 Find the largest positive integer n for which we can find a set of distinct positive integers, such that each integer is at most 2002 and if a, b are in the set, then a 2 and ab are not. Solution
: 1958. For example, {45, 46, ... , 2002}. The set {45, 46, ... , 2002} meets the criterion because the product of any two elements (equal or not) is at least 45 2 = 2025 > 2002 and hence not in the set. The set must exclude 1 (because 1 2 = 1). If the set includes 2, then it must exclude at least one element of each of the pairs (3, 6), (5, 10), (7, 14), ... , (93, 186). So it excludes at least 46 elements and is not maximal. Similarly, if the set includes 3, then it must exclude at least one element of each of the pairs (4, 12), (7, 21), (10, 30), (13, 39), ... , (139, 417). So it excludes at least 46 elements and is not maximal. Similarly, for 4, 5 and 6. The set must also exclude at least one element of each of the 38 disjoint pairs (7, 7 2 ), (8, 8 2 ), (9, 9 2 ), ... , (44, 44 2 ). So we have excluded 44 elements (1 to 6 and one each from 38 pairs). So 1958 is maximal. 23rd Aus 2002 (C) John Scholes jscholes@kalva.demon.co.uk 26 July 2002