35th Putnam 1974 Problem A1 S is a subset of {1, 2, 3, ... , 16} which does not contain three integers which are relatively prime in pairs. How many elements can S have? Solution
: 11 {2, 4, 6, 8, 10, 12, 14, 16, 3, 9, 15} has 11 elements. Any three integers from it include two which are multiples of 2 or two which are multiples of 3, so it does not contain three integers which are relatively prime in pairs. On the other hand, any subset of 12 elements must include at least 3 members of {1, 2, 3, 5, 7, 11, 13} and those 3 will be relatively prime in pairs. 35th Putnam 1974 © John Scholes jscholes@kalva.demon.co.uk 18 Aug 2001