Year: 1974
Topic: Number Theory Combinatorics

Problem:
Call a set of positive integers "conspiratorial" if no three of them are pairwise relatively prime. (A set of integers is "pairwise relatively prime" if no pair of them has a common divisor greater than 1.) What is the largest number of elements in any "conspiratorial" subset of the integers 1 through 16?

Solution:
A conspiratorial subset (CS) of \{1, 2, \dots, 16\} has at most two numbers from the pairwise relatively prime set \{1, 2, 3, 5, 7, 11, 13\} and so has at most $16 - (7 - 2) = 11$ numbers. But \{2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16\} is a CS with 11 elements; hence the answer is \boxed{11}.