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.
© John Scholes
jscholes@kalva.demon.co.uk
11 Dec 2002