Sketch of the Proof:
= number of nonempty subsets of whose average is an integer. Call these subsets int-avg subset (just a name)
Note that one element subsets are by default int-avg subsets. They are n in number. Removing those elements from we are left with int-avg subsets with two or more element. We want to show that the number of such subsets is even.
Let X be the collection of all int-avg subsets S such that the average of S is contained in S
Y be the set of all int-avg subsets S such that the average of S is not contained in S.
Adding or deleting the average of a set to or from that set does not change the average.
This operation sets up a one-to-one correspondence between X and Y, so X and Y have the same cardinality. Since , the number of elements in is even and hence the number of subsets of two or more elements that have an integer average is even.
What is the cardinality of ?