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
Answer: 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 an be the number of multiples of n in S. Then a2 = 140, a3 = 93, a5 = 56, a6 = 46, a10 = 28, a15 = 18, a30 = 9. Hence the number of multiples of 2, 3 or 5 = a2 + a3 + a5 - a6 - a10 - a15 + a30 = 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.
© John Scholes
jscholes@kalva.demon.co.uk
14 Sep 1999