18th Chinese 2003 Problem A2 S is a subset of {1, 2, 3, ... , 100} such that given any two elements a, b in S, there is an element c in S coprime to a and b, and there is an element d in S which has a common factor with a and a common factor with b. What is the largest possible number of elements in S?
72 Solution Thanks to Polly T Wang Let S be the set of all integers n ≤ 100 divisible by just one or two elements of T = {2, 3, 5, 7, 11}. If m, n are two elements in S, then they can be divisible by at most four elements of T, so the fifth member of T is relatively prime to m and n. does not divide either. Also we can pick a prime p in T which divides m and a prime q in T which divides n. If p = q, then p is in S and has a common factor with m and n. If p and q are unequal, then pq is in S and has a common factor with m and n. The 50 even numbers 2, 4, ... , 100 are in S, except for 30, 60, 90, 42, 84, 66, 70, giving 43 members. The odd multiples of 3 are also in S - 3, 9, 15, ... , 99, giving a further 17 members. The multiples of 5 not divisible by 2 or 3 are in S - 5, 25, 35, 55, 65, 85, 95, giving a further 7 members. Finally, 7, 49, 77, 91, 11 are in S, giving a total of 72 members. We show that we cannot do better. Clearly 1 ∉ S. There are 21 primes > 10: 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Not more than one of these primes can be in S, for if two were in S, then the smallest number having a common factor with both is > 100. So we have a total so far of 1 + 20 = 21 exclusions. Suppose no prime > 10 is in S. Then 3 and 70 cannot both be in S, because there cannot be an element coprime to both. Similarly, at least one of (5,42), (7,30), (6,35), (10,21), (14,15), (28,45) is not in S. So we have an additional 1 (the other prime > 10) + 7 (one from each of 7 pairs) = 8 exclusions and hence a total of 29 exclusions, so S cannot have more than 71 members. So suppose there is a prime p > 10 in S. (1) If 7p ∈ S, then 30, 60, 90 ∉ S (because there is no available number coprime to both). If 7p ∉ S, then 7, 49, 77, 91 ∉ S (if 7 and p are in S, then 7p must be in S). (2) if 5p ∈ S, then 42, 84 ∉ S. If 5p ∉ S, then 5, 25 ∉ S. (3) one of 3p, 70 is not in S. (4) one of 6p, 35 is not in S. (5) if 5p and 7p are not in S, then 35 is not in S. If p = 11 or 13, then (1), (2), (3), (4) exclude 3+2+1+1 = 7 elements. If p = 17 or 19, then 7p ∉ S, so (1) excludes 4 elements and (1), (2), (3) exclude 4+2+1 = 7 elements. If p ≥ 23, then (1), (2), (5) exclude 4+2+1 = 7 elements. So we always get at least 21 + 7 = 28 exclusions, implying that S has at most 72 elements. 18th Chinese 2003 © John Scholes jscholes@kalva.demon.co.uk9 Aug 2003 Last corrected/updated 9 Aug 2003