TAOCP 5.1.4 Exercise 34
A **tableau shape** (or Young diagram) is a finite set of cells $\lambda \subset \mathbb{N}^2$ such that $(i,j) \in \lambda$ implies $(i',j') \in \lambda$ for all $1 \le i' \le i$, $1 \le j' \le j$.
Section 5.1.4: Tableaux and Involutions
Exercise 34. [25] (T. Nakayama, 1940.) Prove that if a tableau shape contains a hook of length $4b$, it contains a hook of length $b$.
Verified: no
Solve time: 4h28m
A tableau shape (or Young diagram) is a finite set of cells $\lambda \subset \mathbb{N}^2$ such that $(i,j) \in \lambda$ implies $(i',j') \in \lambda$ for all $1 \le i' \le i$, $1 \le j' \le j$.
The hook of a cell $(i,j) \in \lambda$ consists of $(i,j)$ together with all cells to its right in the same row and all cells below it in the same column.
The hook length $h(i,j)$ is the number of cells in that hook.
Theorem. If a tableau shape $\lambda$ contains a hook of length $4b$ ($b\ge 1$), then it contains a hook of length $b$.
Proof. We proceed by induction on the number of cells $n = |\lambda|$.
Base case: $n = 4b$.
If a shape with exactly $4b$ cells contains a hook of length $4b$, the shape must be exactly that hook - a hook shape consisting of a first row of length $A+1$ and a first column of length $B+1$ with $A+B+1 = 4b$ (so $A+B = 4b-1$). The hook lengths of its cells are
$$4b,; A,; A-1,;\dots,;1,; B,; B-1,;\dots,;1.$$
Since $A+B = 4b-1$, we have $\max(A,B) \ge 2b-1$. For $b=1$ this gives a hook of length $1$; for $b\ge 2$, $2b-1 \ge b$, so the integer $b$ appears among the hook lengths $A, A-1,\dots,1$ or $B, B-1,\dots,1$. Hence a hook of length $b$ exists.
Inductive step. Assume the statement holds for all shapes with fewer than $n$ cells, where $n > 4b$. Let $\lambda$ be a shape with $n$ cells that contains a hook of length $4b$ but no hook of length $b$. Let $(r,c)$ be a cell of $\lambda$ with hook length $4b$.
If $\lambda$ is a hook shape, then $n = 4b$, contradicting $n > 4b$. Hence $\lambda$ has at least two corners.
Case 1: All corners of $\lambda$ lie in the hook of $(r,c)$.
Then every corner is either in row $r$ or in column $c$. This forces $\lambda$ to be a fat hook: there exist integers $A,B \ge 0$ such that the row lengths are
$$\lambda_1 = \cdots = \lambda_r = c+A,\qquad \lambda_{r+1} = \cdots = \lambda_{r+B} = c,$$
and no other rows exist (so the total number of rows is $r+B$). The hook at $(r,c)$ has arm length $A = \lambda_r - c$ and leg length $B = \lambda'_c - r$, satisfying $A+B+1 = 4b$.
We now show that such a shape always contains a hook of length $b$. The hook lengths in the arm (row $r$) are $4b, 4b-1, \dots, 4b-A$; the hook lengths in the leg (column $c$) are $4b, 4b-1, \dots, 4b-B$. The hook lengths in the top‑left $r \times c$ rectangle are $4b + h$ where $h$ runs through the hook lengths of an $r \times c$ rectangle. The smallest hook length there is $4b$ (at $(r,c)$). Hence $b$ cannot appear in that rectangle. The only remaining hook lengths are those in the top‑right $r \times A$ rectangle and the bottom‑left $B \times c$ rectangle. The hook lengths in an $r \times A$ rectangle are exactly all integers from $1$ to $r+A-1$; those in a $B \times c$ rectangle are all integers from $1$ to $B+c-1$. Since $A+B = 4b-1$, we have $$r+A-1 \ge A \quad\text{and}\quad B+c-1 \ge B.$$ If $A \ge b$ then $b \le A \le r+A-1$, so $b$ appears in the top‑right rectangle. If $B \ge b$ then $b$ appears in the bottom‑left rectangle. If both $A < b$ and $B < b$, then $A \le b-1$ and $B \le b-1$, so $A+B \le 2b-2$, contradicting $A+B = 4b-1 \ge 2b-1$ for $b \ge 1$. Therefore one of $A,B$ is at least $b$, and the shape contains a hook of length $b$. This contradicts our assumption that $\lambda$ has no such hook. Hence Case 1 cannot occur.
Case 2: There exists a corner of $\lambda$ not in row $r$ and not in column $c$.
Among all such corners choose one $(p,q)$ with the maximum value of $p+q$. Remove this corner to obtain a shape $\lambda'$ with $n-1$ cells. Because $(p,q)$ is not in the hook of $(r,c)$, the hook of $(r,c)$ is unchanged in $\lambda'$; its length remains $4b$. By the induction hypothesis, $\lambda'$ contains a hook of length $b$; let $(x,y)$ be the cell of that hook in $\lambda'$.
In the original shape $\lambda$ the hook length of $(x,y)$ is either $b$ (if the removed corner was not in that hook) or $b+1$ (if it was). Since $\lambda$ has no hook of length $b$, the latter must happen: $h_\lambda(x,y) = b+1$ and the removed corner $(p,q)$ lies in the hook of $(x,y)$ in $\lambda$. Because $(p,q)$ is a corner, it can only be the end of the arm or the end of the leg of $(x,y)$. By symmetry (transposing the diagram if necessary) we may assume it is the end of the arm, so $$x = p,\qquad y < q,$$ and the arm of $(x,y)$ runs from column $y$ to $q$. Note that $p \neq r$ and $q \neq c$ because $(p,q)$ is outside the hook of $(r,c)$. The choice of $(p,q)$ with maximal $p+