22nd Putnam 1961 Problem A5 Let X be a set of n points. Let P be a set of subsets of X, such that if A, B ∈ P, then X - A, A ∪ B, A ∩ B ∈ P. What are the possible values for the number of elements of P? Solution
: 2, 4, 8, ... , 2 n . Take 0 ≤ r < n. Let A 1 = {1}, A 2 = {2} , ... , A r = {r}, A r+1 = {r+1, r+2, ... , n}. Consider the collection of all unions of sets A i . This collection has 2 r+1 elements and satisfies the conditions. So this shows that we can achieve the values 2, 4, 8, ... , 2 n . To prove the converse we use induction on n. It is obviously true for n = 1. Suppose it is true for all n < N. Let X have N points and P be a set of subsets of X satisfying the condition. If |P| = 2, then there is nothing to prove. Otherwise we can find a member Y of P other than the empty set and X which has no non-trivial subsets in P. Now consider the collection Q of subsets of X - Y which are in P. It is easy to check that (1) P is just the collection of all A and A ∩ Y, where A is in Q, so that |P| = 2|Q|, and (2) Q satisfies the conditions, so |Q| is a power of 2 by induction. 22nd Putnam 1961 © John Scholes jscholes@kalva.demon.co.uk 15 Feb 2002