Putnam 2002, Problem A-3

Let $n \geq 2$ be an integer and $T_n$ be the number of non-empty subsets $S$ of $\{1,2,3,\ldots,n\}$ with the property that the average of the elements of $S$ is an integer. Prove that $T_n - n$ is always even.

Solution:
Note that each of the sets \( \{1\}, \{2\}, \ldots, \{n\} \) has the desired property. Moreover, for each set \( S \) with integer average \( m \) that does not contain \( m \), \( S \cup \{m\} \) also has average \( m \), while for each set \( T \) of more than one element with integer average \( m \) that contains \( m \), \( T \setminus \{m\} \) also has average \( m \). Thus the subsets other than \( \{1\}, \{2\}, \ldots, \{n\} \) can be grouped in pairs, so \( T_n - n \) is even.