CMO 2017 Problem 3

Let $n$ be a positive integer, and define $S_{n}=\{1,2, \ldots, 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 \geq 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$. $)$