IMO 1991 SL 12

Origin: CHN

Problem

Let S = {1, 2, 3, . . ., 280}. Find the minimal natural num- ber n such that in any n-element subset of S there are five numbers that are pairwise relatively prime.

Solution

Let Am be the set of those elements of S which are divisible by m. By the inclusion-exclusion principle, the number of elements divisible by 2, 3, 5 or 7 equals |A2 \cupA3 \cupA5 \cupA7| = |A2| + |A3| + |A5| + |A7| −|A6| −|A10| −|A14| −|A15| −|A21| −|A35| + |A30| + |A42| + |A70| + |A105| −|A210| = 140 + 93 + 56 + 40 −46 −28 −20 −18 −13 −8 + 9 + 6 + 4 + 2 −1 = 216. Among any five elements of the set A2 \cupA3 \cupA5 \cupA7, one of the sets A2, A3, A5, A7 contains at least two, and those two are not relatively prime. Therefore n > 216.

We claim that the answer is n = 217. First notice that the set A2 \cupA3 \cup A5 \cupA7 consists of four prime (2, 3, 5, 7) and 212 composite numbers. The set S \ A contains exactly 8 composite numbers: namely, 112, 11 \cdot 13, 11 \cdot 17, 11 \cdot 19, 11 \cdot 23, 132, 13 \cdot 17, 13 \cdot 19. Thus S consists of the unity, 220 composite numbers and 59 primes. Let A be a 217-element subset of S, and suppose that there are no five pairwise relatively prime numbers in A. Then A can contain at most 4 primes (or unity and three primes) and at least 213 composite numbers. Hence the set S \ A contains at most 7 composite numbers. Consequently, at least one of the following 8 five-element sets is disjoint with S \ A, and is thus entirely contained in A: {2 \cdot 23, 3 \cdot 19, 5 \cdot 17, 7 \cdot 13, 11 \cdot 11}, {2 \cdot 29, 3 \cdot 23, 5 \cdot 19, 7 \cdot 17, 11 \cdot 13}, {2 \cdot 31, 3 \cdot 29, 5 \cdot 23, 7 \cdot 19, 11 \cdot 17}, {2 \cdot 37, 3 \cdot 31, 5 \cdot 29, 7 \cdot 23, 11 \cdot 19}, {2 \cdot 41, 3 \cdot 37, 5 \cdot 31, 7 \cdot 29, 11 \cdot 23}, {2 \cdot 43, 3 \cdot 41, 5 \cdot 37, 7 \cdot 31, 13 \cdot 17}, {2 \cdot 47, 3 \cdot 43, 5 \cdot 41, 7 \cdot 37, 13 \cdot 19}, {2 \cdot 2, 3 \cdot 3, 5 \cdot 5, 7 \cdot 7, 13 \cdot 13}. As each of these sets consists of five numbers relatively prime in pairs, the claim is proved.