The problem is to prove that there is an odd number of nonempty subsets $T$ of $S_n$ such that the average $A(T)$ and median $M(T)$ satisfy $A(T) = M(T)$. Given a subset $T$, consider the subset $T^* = \{n+1-t : t \in T\}$. It holds that $A(T^*) = n+1 - A(T)$ and $M(T^*) = n+1 - M(T)$, which implies that if $A(T) = M(T)$ then $A(T^*) = M(T^*)$. Pairing each set $T$ with $T^*$ yields that there are an even number of sets $T$ such that $A(T) = M(T)$ and $T \neq T^*$.

Thus it suffices to show that the number of nonempty subsets $T$ such that $A(T) = M(T)$ and $T = T^*$ is odd. Now note that if $T = T^*$, then $A(T) = M(T) = \frac{n+1}{2}$. Hence it suffices to show the number of nonempty subsets $T$ with $T = T^*$ is odd. Given such a set $T$, let $T'$ be the largest nonempty subset of $\{1, 2, \ldots, \lceil n / 2 \rceil\}$ contained in $T$. Pairing $T$ with $T'$ forms a bijection between these sets $T$ and the nonempty subsets of $\{1, 2, \ldots, \lceil n / 2 \rceil\}$. Thus there are $2^{\lceil n / 2 \rceil} - 1$ such subsets, which is odd as desired.