CMO 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^{\ast }=\{n+1-t:t\in T\}$. It holds that $A(T^{\ast })=n+1-A(T)$ and $M(T^{\ast })=n+1-M(T)$, which implies that if $A(T)=M(T)$ then $A(T^{\ast })=M(T^{\ast })$. Pairing each set $T$ with $T^{\ast }$ yields that there are an even number of sets $T$ such that $A(T)=M(T)$ and $T\ne T^{\ast }$.

Thus it suffices to show that the number of nonempty subsets $T$ such that $A(T)=M(T)$ and $T=T^{\ast }$ is odd. Now note that if $T=T^{\ast }$, then $A(T)=M(T)=\frac{n+1}{2}$. Hence it suffices to show the number of nonempty subsets $T$ with $T=T^{\ast }$ is odd. Given such a set $T$, let $T^{\prime }$ be the largest nonempty subset of $\{1,2,\dots ,\lceil n/2\rceil \}$ contained in $T$. Pairing $T$ with $T^{\prime }$ 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$

---

Alternative solution.

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^{\ast }=\{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.