### 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**

Answer: 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