Question 142
Let $n$ be a positive integer, and define $S_n = \{1, 2, \dots, n\}$. Consider a non-empty subset $T$ of $S_n$. We say that $T$ is balanced if the median of $T$ is equal to the average of $T$. For example, for $n = 9$, each of the subsets $\{7\}$, $\{2, 5\}$, $\{2, 3, 4\}$, $\{5, 6, 8, 9\}$, and $\{1, 4, 5, 7, 8\}$ is balanced; however, the subsets $\{2, 4, 5\}$ and $\{1, 2, 3, 5\}$ are not balanced. For each $n \ge 1$, prove that the number of balanced subsets of $S_n$ is odd.
(To define the median of a set of $k$ numbers, first put the numbers in increasing order; then the median is the middle number if $k$ is odd, and the average of the two middle numbers if $k$ is even. For example, the median of $\{1, 3, 4, 8, 9\}$ is $4$, and the median of $\{1, 3, 4, 7, 8, 9\}$ is $(4+7)/2 = 5.5$.)
(To define the median of a set of $k$ numbers, first put the numbers in increasing order; then the median is the middle number if $k$ is odd, and the average of the two middle numbers if $k$ is even. For example, the median of $\{1, 3, 4, 8, 9\}$ is $4$, and the median of $\{1, 3, 4, 7, 8, 9\}$ is $(4+7)/2 = 5.5$.)