, 2017

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, \dots, \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, \dots, \lceil n/2 \rceil\}$. Thus there are $2^{\lceil n/2 \rceil} - 1$ such subsets, which is odd as desired. $\square$

Using the notation from the above solution: Let $B$ be the number of subsets $T$ with $M(T) > A(T)$, $C$ be the number with $M(T) = A(T)$, and $D$ be the number with $M(T) < A(T)$. Pairing each set $T$ counted by $B$ with $T^* = \{n+1-t: t \in T\}$ shows that $B = D$. Now since $B + C + D = 2^n - 1$, we have that $C = 2^n - 1 - 2B$, which is odd.