A Young tableau is a 2D array of integers increasing from left to right and…
2015
A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with ∞, and hence there cannot be any entry to the right of, or below a ∞. The following Young tableau consists of unique entries.
\(\begin{array}{|l|l|l|l|}\hline \textbf{1} & \text{2}& \text{5} & \text{14} \\\hline \text{3} & \text{4} & \text{6} & \text{23} \\\hline \text{10} & \text{12} & \text{18} & \text{25} \\\hline \text{31} & \text{$\infty$} & \text{$\infty$} & \text{$\infty$} \\\hline \end{array}\)
When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a ∞). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is ______________.
Attempted by 105 students.
Show answer & explanation
Correct answer: 5
Answer: 5 entries must be shifted.
Key idea: Repeatedly replace the empty cell created by removing the element with the smaller of its right and down neighbors, moving that neighbor into the hole. Continue until an infinity is moved into the hole. Each finite entry moved (other than the removed element) counts as one shift.
Remove 1 at position (row 1, column 1). Hole is at (1,1). Compare right = 2 and down = 3; move 2 into the hole. (shifts = 1)
Hole is now at (1,2). Compare right = 5 and down = 4; move 4 into the hole. (shifts = 2)
Hole is now at (2,2). Compare right = 6 and down = 12; move 6 into the hole. (shifts = 3)
Hole is now at (2,3). Compare right = 23 and down = 18; move 18 into the hole. (shifts = 4)
Hole is now at (3,3). Compare right = 25 and down = ∞; move 25 into the hole. (shifts = 5)
Hole is now at (3,4). Both neighbors are ∞, so place ∞ into the hole and stop.
Total number of finite entries moved (excluding the removed 1) = 5.
Why this is minimal: The described rule (always pulling the smaller neighbor) is the only way to maintain the increasing rows and columns at each step. Any other choice would violate the Young tableau property. Therefore the sequence above is the valid sequence of moves and its count is minimal.
A video solution is available for this question — log in and enroll to watch it.