### 63rd Putnam 2002

**Problem A3**

A subset of {1, 2, ... , n} is *round* if it is non-empty and the average (arithmetic mean) of its elements is an integer. Show that the number of round subsets of {1, 2, ... , n} has the same parity as n.

**Solution**

Given a subset S of {1, 2, ... , n}, let S' be the subset {n+1-k | k is in S}. Note that the average of the elements of S is integral iff the average of the elements of S' is integral. We look separately at n odd and n even.

Suppose n is odd. The subsets S such that S ≠ S' divide into pairs S, S'. So there are an even number of subsets S with integral average and S ≠ S'. With one exception, the non-empty subsets S with S = S' divide into pairs T, T ∪ {(n+1)/2} (where (n+1)/2 is not a member of T). If T = T' then T has average (n+1)/2, so either both or neither of T, T ∪ {(n+1)/2} have integral average. The exception is the subset { (n+1)/2 } (where the corresponding member of the pair is empty). Thus the number of non-empty subsets S with integral average and S = S' is odd. So the result is true for n odd.

The case n even is simpler, because we cannot have S = S' for a subset with integral average (the average is (n+1)/2, which is not integral). So the subsets with integral average form pairs S, S'. Hence the number of such subsets is even.

*Alternative solution*

We can divide the subsets with integral average and more than one element into pairs, one of which contains the average and one of which does not.

63rd Putnam 2002

© John Scholes

jscholes@kalva.demon.co.uk

11 Dec 2002