GATE 2015 CS (CS2) – Question 48
A Young tableau has unique finite entries increasing along rows and columns; empty cells are ∞, with no finite entry to the right of or below an empty cell. It is $$\begin{pmatrix}1&2&5&14\\3&4&6&23\\10&12&18&25\\31&\infty&\infty&\infty\end{pmatrix}.$$ After removing 1, what is the minimum number of other entries moved to restore a valid tableau?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 5
Explanation
Move the smaller right/down neighbour into the hole repeatedly. The forced moves are 2, then 4, then 6, then 18, then 25; the final hole can become infinity. These five moves follow a shortest admissible hole path while preserving both row and column order. Thus five other entries move.