Question 41

Deleting the minimum element $1$ at cell $(0, 0)$ leaves a vacancy. To restore the Young tableau invariant, repeatedly compare the right neighbor $(r, c+1)$ and the bottom neighbor $(r+1, c)$, shifting the smaller of the two into the vacant cell $(r, c)$.

Trace of shifts:

1. At $(0, 0)$, right neighbor is $(0, 1) = 2$, down neighbor is $(1, 0) = 3$.
   • $\min(2, 3) = 2$. Shift $2$ from $(0, 1)$ to $(0, 0)$. Vacancy moves to $(0, 1)$. (Shift 1)
2. At $(0, 1)$, right neighbor is $(0, 2) = 5$, down neighbor is $(1, 1) = 4$.
   • $\min(5, 4) = 4$. Shift $4$ from $(1, 1)$ to $(0, 1)$. Vacancy moves to $(1, 1)$. (Shift 2)
3. At $(1, 1)$, right neighbor is $(1, 2) = 6$, down neighbor is $(2, 1) = 12$.
   • $\min(6, 12) = 6$. Shift $6$ from $(1, 2)$ to $(1, 1)$. Vacancy moves to $(1, 2)$. (Shift 3)
4. At $(1, 2)$, right neighbor is $(1, 3) = 23$, down neighbor is $(2, 2) = 18$.
   • $\min(23, 18) = 18$. Shift $18$ from $(2, 2)$ to $(1, 2)$. Vacancy moves to $(2, 2)$. (Shift 4)
5. At $(2, 2)$, right neighbor is $(2, 3) = 25$, down neighbor is $(3, 2) = \infty$.
   • $\min(25, \infty) = 25$. Shift $25$ from $(2, 3)$ to $(2, 2)$. Vacancy moves to $(2, 3)$. (Shift 5)
6. At $(2, 3)$, down neighbor is $(3, 3) = \infty$, right is boundary. The vacancy is filled with $\infty$.

The elements shifted into place are $2, 4, 6, 18, 25$.
The total number of shifted entries (other than 1) is 5.