IMO 1991 Problem A3 Let S = {1, 2, 3, ... 280}. Find the smallest integer n such that each n-element subset of S contains five numbers which are pairwise relatively prime. Solution
: 217. Let A be the subset of all multiples of 2, 3, 5 or 7. Then A has 216 members and every 5-subset has 2 members with a common factor. [To show that |A| = 216, let a n be the number of multiples of n in S. Then a 2 = 140, a 3 = 93, a 5 = 56, a 6 = 46, a 10 = 28, a 15 = 18, a 30 = 9. Hence the number of multiples of 2, 3 or 5 = a 2 + a 3 + a 5 - a 6 - a 10 - a 15 + a 30 = 206. There are ten additional multiples of 7: 7, 49, 77, 91, 119, 133, 161, 203, 217, 259.] Let P be the set consisting of 1 and all the primes < 280. Define: A1 = {2·41, 3·37, 5·31, 7·29, 11·23, 13·19} A2 = {2·37, 3·31, 5·29, 7·23, 11·19, 13·17} A3 = {2··31, 3·29, 5·23, 7·19, 11·17, 13·13} B1 = {2·29, 3·23, 5·19, 7·17, 11·13} B2 = {2·23, 3·19, 5·17, 7·13, 11·11} Note that these 6 sets are disjoint subsets of S and the members of any one set are relatively prime in pairs. But P has 60 members, the three As have 6 each, and the two Bs have 5 each, a total of 88. So any subset T of S with 217 elements must have at least 25 elements in common with their union. But 6·4 = 24 < 25, so T must have at least 5 elements in common with one of them. Those 5 elements are the required subset of elements relatively prime in pairs. Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X. 32nd IMO 1991 © John Scholes jscholes@kalva.demon.co.uk 14 Sep 1999