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
Answer: 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.
© John Scholes
jscholes@kalva.demon.co.uk
18 Aug 2001