Putnam 2024, Problem A-3

Let \( S \) be the set of bijections
\[ T: \{1,2,3\} \times \{1,2,\ldots,2024\} \to \{1,2,\ldots,6072\} \]
such that \( T(1,j) < T(2,j) < T(3,j) \) for all \( j \in \{1,2,\ldots,2024\} \) and \( T(i,j) < T(i,j+1) \) for all \( i \in \{1,2,3\} \) and \( j \in \{1,2,\ldots,2023\} \). Do there exist \( a \) and \( c \) in \( \{1,2,3\} \) and \( b \) and \( d \) in \( \{1,2,\ldots,2024\} \) such that the fraction of elements \( T \) in \( S \) for which \( T(a,b) < T(c,d) \) is at least \( 1/3 \) and at most \( 2/3 \)?

Solution:
Yes, such $a,b,c,d$ exist: we take
$$(a,b) = (2,1), \quad (c,d) = (1,2).$$

We will represent $T$ as an $3 \times n$ array (3 rows, $n$ columns) of integers in which each of $1,\ldots,3n$ occurs exactly once and the rows and columns are strictly increasing; we will specialize to $n = 2024$ at the end.

We first note that $T(1,1) = 1$ and $2 \in \{T(1,2),T(2,1)\}$. From this, it follows that $T(2,1) < T(1,2)$ if and only if $T(2,1) = 2$.

We next recall a restricted form of the hook length formula (see the first remark for a short proof of this restricted version and the second remark for the statement of the general formula). Consider more generally an array consisting of (up to) three rows of lengths $n_1 \geq n_2 \geq n_3 \geq 0$, aligned at the left. Let $f(n_1,n_2,n_3)$ be the number of ways to fill this array with a permutation of the numbers $1,\ldots,n_1 + n_2 + n_3$ in such a way that each row increases from left to right and each column increases from top to bottom. The hook length formula then shows that $f(n_1,n_2,n_3)$ equals
$$\frac{(n_1 - n_2 + 1)(n_1 - n_3 + 2)(n_2 - n_3 + 1)(n_1 + n_2 + n_3)!}{(n_1 + 2)!(n_2 + 1)!n_3!}.$$

We then note that if $T(2,1) = 2$, we obtain a array with row lengths $n,n-1,n-1$ by removing $1$ and $2$, relabeling each remaining $i$ as $3n + 1 - i$, and reflecting in both axes. The probability that $T(2,1) < T(1,2)$ is thus
$$\frac{f(n,n-1,n-1)}{f(n,n,n)} = \frac{(2)(3)(n+1)n}{(1)(2)(3n)(3n-1)} = \frac{n+1}{3n-1} = \frac{1}{3} + \frac{4}{9n-3},$$
this is always greater than $\frac{1}{3}$, and for $n = 2024$ it is visibly less than $\frac{2}{3}$.

**Remark.** We prove the claimed formula for $f(n_1,n_2,n_3)$ by induction on $n_1 + n_2 + n_3$. To begin with, if $n_2 = n_3 = 0$, then the desired count is indeed $f(n_1,0,0) = 1$. Next, suppose $n_2 > 0, n_3 = 0$. The entry $n_1 + n_2$ must go at the end of either the first or second row; counting ways to complete the diagram from these starting points yields
$$f(n_1,n_2,0) = f(n_1-1,n_2,0) + f(n_1,n_2-1,0).$$

(This works even if $n_1 = n_2$, in which case the first row is not an option but correspondingly $f(n_2-1,n_2,0) = 0$.) The induction step then follows from the identity
$$\frac{(n_1 - n_2)(n_1 + 1) + (n_1 - n_2 + 2)n_2}{(n_1 - n_2 + 1)(n_1 + n_2)} = 1.$$

(As an aside, the case $n_1 = n_2, n_3 = 0$ recovers a standard interpretation of the Catalan numbers.)

Finally, suppose $n_3 > 0$. We then have
$$f(n_1,n_2,n_3) = f(n_1-1,n_2,n_3) + f(n_1,n_2-1,n_3) + f(n_1,n_2,n_3-1),$$
and the induction step now reduces to the algebraic identity
$$\frac{(n_1 - n_2)(n_1 - n_3 + 1)(n_1 + 2)}{(n_1 - n_2 + 1)(n_1 - n_3 + 2)(n_1 + n_2 + n_3)} + \frac{(n_1 - n_2 + 2)(n_2 - n_3)(n_2 + 1)}{(n_1 - n_2 + 1)(n_2 - n_3 + 1)(n_1 + n_2 + n_3)} + \frac{(n_1 - n_3 + 3)(n_2 - n_3 + 2)n_3}{(n_1 - n_3 + 2)(n_2 - n_3 + 1)(n_1 + n_2 + n_3)} = 1.$$

**Remark.** We formulate the general hook length formula in standard terminology. Let $N$ be a positive integer, and consider a semi-infinite checkerboard with top and left edges. A Ferrers diagram is a finite subset of the squares of the board which is closed under taking a unit step towards either edge. Given a Ferrers diagram with $N$ squares, a standard Young tableau for this diagram is a bijection of the squares of the diagram with the integers $1,\ldots,N$ such that the numbers always increase under taking a unit step away from either edge.

For each square $s = (i,j)$ in the diagram, the hook length $h_s$ of $s$ is the number of squares $(i',j')$ in the diagram such that either $i = i', j \leq j'$ or $i \leq i', j = j'$ (including $s$ itself). Then the number of standard Young tableaux for this diagram equals
$$\frac{N!}{\prod_s h_s}.$$

For a proof along the lines of the argument given in the previous remark, see: Kenneth Glass and Chi-Keung Ng, A simple proof of the hook length formula, American Mathematical Monthly 111 (2004), 700-704.