Problem: Let $S=\{1,2, \ldots, 2008\}$. For any nonempty subset $A$ of $S$, define $m(A)$ to be the median of $A$. (If $A$ has an even number of elements, $m(A)$ is the average of the middle elements.) Determine the average of $m(A)$, when $A$ is taken over all nonempty subsets of $S$. Solution: We want to control $m(A)$. To do this, by some witchcraft, we may notice that we can define an involution $f: \mathcal{P}(S) \backslash \emptyset \to \mathcal{P}(S) \backslash \emptyset$ by $f(A) = \{2009-x: x \in A \}$. Now, if we have $A \in \mathcal{P}(S) \backslash \emptyset$, we see that $m(A) = 2009 - m(f(A))$. This is because if $k$ is the median of $A$, then we know in $f(A)$, all elements are subtracted from $2009$ and so the 'middle element' is preserved (just mirrored) and is $2009-k$. So, $m(A) + m(f(A)) = 2009$ for any $A$. In particular, $\frac{m(A) + m(f(A))}{2} = \frac{2009}{2}$. When $A = f(A)$, we have $m(A) = m(f(A))$ and still $m(A) = 2009-m(f(A)) \implies m(A) = \frac{2009}{2}$. Define $g(A) = \frac{m(A) + m(f(A))}{2} = \frac{2009}{2}$. Consider the sum $\sum_{A \subseteq S}g(A) = \sum_{A \subseteq S} \frac{m(A) + m(f(A))}{2}$. Notice that this sum *is* just $\sum_{A \subseteq S}m(A)$ because when $A \neq f(A)$, we have that $\frac{m(A) + m(f(A))}{2}$ is contributed twice in the sum (giving just $m(A) + m(f(A))$ and when $m(A) = m(f(A))$, $m(A)$ is only contributed once. This sum represents the numerator of the average. Namely, in the average, we have $ \sum_{A \in \mathcal{P}(S) \backslash \emptyset}\frac{m(A)}{2^{2008}-1} = \frac{2^{2008}-1\left( \frac{2009}{2}\right)}{2^{2008}-1} = \frac{2009}{2} $