13th Chinese 1998 Problem A3 Let X = {1, 2, ... , 98}. Call a subset of X good iff (1) it has 10 elements, and (2) if it is partitioned in any way into two subsets of 5 elments, then one subset has an element comprime to each of the other 4, and the other subset has an element which is not coprime to any of the other 4. Find the smallest n such that any subset of X of n elements has a good subset.
50 Solution Obviously n > 49, for the set {2, 4, 6, ... , 98} has 49 elements and all the elements in any subset of 5 elements have a common factor 2. We show that if n = 50, then we can find a good subset. Let Y be a subset with 50 elements. Let e(Y) be the number of even numbers in Y. We consider several cases depending on the value of e(Y). Note first that if Y contains an odd element x which is coprime to at least 9 even elements of Y, then Y is good. For take Z to be x and 9 even elements of Y coprime to x. Suppose Z is partitioned into A and B. wlog x ∈ A. Then x is coprime to the other elements of A. All elements of B have a factor 2, so no two elements of B are coprime. Hence Z is good. Case 1 . e(Y) ≥ 31. Y has at most 49 even elements, so it must have an odd element x. Since x  7, then there are at most [98/14] = 7 even numbers in X having a common factor with x. If x = pq with p > 5, then there are at most [98/14] + [98/22] = 11 even numbers in X having a common factor with x. So in any case there are at most 12. Hence there are at least 21 - 12 = 9 even numbers in Y which are coprime to x, and the result is established. Case 3 . 11 ≤ e(Y) ≤ 20. So Y has at least 30 odd numbers. X has 16 odd members with smallest prime divisor 3, 7 odd members with smallest prime divisor 5 (namely 5, 25, 35, 55, 65, 85, 95), 4 odd members with smallest prime divisor 7 (namely 7, 49, 77, 91), and 1 odd member whose smallest prime divisor is p where 97 ≥ p > 7. Since 16 + 7 + 4 + 1 + 1 = 29, we can pick x to have smallest prime divisor p ≥ 17. So there are at most [98/34] = 2 even members of X having a common factor with x. Hence there are at least 9 even members of Y coprime to x, and the result is established. Case 4 . e(Y) = 9 or 10. So Y has at least 40 odd members. So it must contain at least one of the primes 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. So take x to be a prime ≥ 53. Then there are no even numbers in Y which have a common factor with x, and hence at least 9 which are coprime to x, and the result is established. Case 5 . e(Y) ≤ 8. So Y has at least 42 odd members. So it must contain at least one of the primes 61, 67, ... , 97. Take x to be a prime ≥ 61 in Y. X has 16 multiples of 3. Since Y fails to contain at most 7 of the odd numbers, it must include at least 9 multiples of 3. So take Z to be x and 9 multiples of 3. Then Z isgood (by the same argument as para 2 above). 13th Chinese 1998 © John Scholes jscholes@kalva.demon.co.uk 13 January 2004 Last corrected/updated 13 Jan 04