Harvard-MIT Mathematics Tournament

Solution:

Call an element $t \in S$ an involution if and only if $t^{2}$ is the identity permutation. We claim that the set of all involutions in $S$ constitutes a good subset of $S$. The proof is simple. Let $s$ be an arbitrary permutation in $S$. Note that $s$ may be decomposed into a product of disjoint cycles of length at least $2$, and suppose that there are $m$ such cycles in its decomposition. For $1 \leq i \leq m$, let $l_{i}$ denote the length of the $i$th cycle, so that $s$ may be written as
$$\left(a_{1,1} a_{1,2} \ldots a_{1, l_{1}}\right)\left(a_{2,1} a_{2,2} \ldots a_{2, l_{2}}\right) \ldots\left(a_{m, 1} a_{m, 2} \ldots a_{m, l_{m}}\right)$$
for some pairwise distinct elements
$$a_{1,1}, a_{1,2}, \ldots, a_{1, l_{1}}, a_{2,1}, a_{2,2}, \ldots, a_{2, l_{2}}, \ldots, a_{m, 1}, a_{m, 2}, \ldots, a_{m, l_{m}}$$
of $[n]$. Consider the permutations $q$ and $r$ defined by $q\left(a_{i, j}\right)=a_{i, l_{i}+1-j}$ for all $1 \leq j \leq l_{i}$ and $r\left(a_{i, 1}\right)=a_{i, 1}$ and $r\left(a_{i, k}\right)=a_{i, l_{i}+2-k}$ for all $2 \leq k \leq l_{i}$, for all $1 \leq i \leq m$, and by $q(x)=r(x)=x$ for all $x \in[n]$ otherwise. Since $q, r \in S$, $q^{2}=r^{2}=1$, and $r q=s$, it follows that the set of all involutions in $S$ is indeed good, as desired.

For all integer partitions $\lambda$ of $n$, let $f^{\lambda}$ denote the number of standard Young tableaux of shape $\lambda$. By the Robinson-Schensted-Knuth correspondence, the permutations of $[n]$ are in bijection with pairs of standard Young tableaux of the same shape in such a way that the involutions of $[n]$ are in bijection with pairs of identical standard Young tableaux. In other words, the number of permutations of $[n]$ is equal to the number of pairs of identically shaped standard Young tableaux whose shape is a partition of $n$, and the number of involutions of $[n]$ is equal to the number of standard Young tableaux whose shape is a partition of $n$. Hence $n!=\sum_{\lambda}\left(f^{\lambda}\right)^{2}$ and $\tau \leq \sum_{\lambda} \frac{f^{\lambda}}{n!}$, where both sums range over all partitions $\lambda$ of $n$.

For all elements $u \in S$, define the conjugacy class of $u$ to be the set of elements that may be written in the form $s^{-1} u s$ for some $s \in S$. It is easy to see that for all $u, u' \in S$, the conjugacy classes of $u$ and $u'$ are either identical or disjoint. It follows that $S$ may be partitioned into disjoint conjugacy classes and that any extremely good subset of $S$ must contain at least one element from each distinct conjugacy class. We claim that the number of distinct conjugacy classes of $S$ is at least the number of integer partitions of $n$. It turns out that the two numbers are in fact equal, but such a result is not necessary for the purposes of this problem. Let $u$ be an arbitrary permutation in $S$. Recall that $u$ may be written as
$$\left(a_{1,1} a_{1,2} \ldots a_{1, l_{1}}\right)\left(a_{2,1} a_{2,2} \ldots a_{2, l_{2}}\right) \ldots\left(a_{m, 1} a_{m, 2} \ldots a_{m, l_{m}}\right)$$
for some pairwise distinct elements
$$a_{1,1}, a_{1,2}, \ldots, a_{1, l_{1}}, a_{2,1}, a_{2,2}, \ldots, a_{2, l_{2}}, \ldots, a_{m, 1}, a_{m, 2}, \ldots, a_{m, l_{m}}$$
of $[n]$. Associate to the conjugacy class of $u$ the partition $n=l_{w_{1}}+l_{w_{2}}+\ldots+l_{w_{m}}+1+\ldots+1$, where $w_{1}, w_{2}, \ldots, w_{m}$ is a partition of $1,2, \ldots, m$ such that $w_{1} \geq w_{2} \geq \ldots \geq w_{m}$ and the $1$'s represent all the fixed points of $s$. Now note that if $s$ is any permutation in $S$, $s^{-1} u s$ may be written in the form
$$s^{-1}\left(a_{1,1} a_{1,2} \ldots a_{1, l_{1}}\right) s s^{-1}\left(a_{2,1} a_{2,2} \ldots a_{2, l_{2}}\right) s \ldots s^{-1}\left(a_{m, 1} a_{m, 2} \ldots a_{m, l_{m}}\right) s$$
which may be written as
$$\left(b_{1,1} b_{1,2} \ldots b_{1, l_{1}}\right)\left(b_{2,1} b_{2,2} \ldots b_{2, l_{2}}\right) \ldots\left(b_{m, 1} b_{m, 2} \ldots b_{m, l_{m}}\right)$$
for some pairwise distinct elements
$$b_{1,1}, b_{1,2}, \ldots, b_{1, l_{1}}, b_{2,1}, b_{2,2}, \ldots, b_{2, l_{2}}, \ldots, b_{m, 1}, b_{m, 2}, \ldots, b_{m, l_{m}}$$
of $[n]$ because multiplying by $s^{-1}$ on the left and by $s$ on the right is equivalent to re-indexing the letters $1,2, \ldots, n$. Hence if partitions of $n$ are associated to all conjugacy classes of $S$ analogously, the same partition that is associated to $u$ is associated to $s^{-1} u s$ for all $s \in S$. Since exactly one partition is associated to each conjugacy class, it follows that the number of conjugacy classes cannot exceed the number of partitions, as desired.

To conclude, we need only observe that $v \geq \sum_{\lambda} \frac{1}{n!}$ by our above claim, for then
$$n!\sqrt{v}=\sqrt{n!\sum_{\lambda} 1}=\sqrt{\left(\sum_{\lambda}\left(f^{\lambda}\right)^{2}\right)\left(\sum_{\lambda} 1\right)} \geq \sum_{\lambda} f^{\lambda} \geq n!\tau$$
by the Cauchy-Schwarz inequality, and this completes the proof.