TAOCP 5.1.4 Exercise 6
Let Algorithm S be the full sequence of insertions described in Algorithm I applied successively, terminating with a tableau $P$ and a final added position $(r,s)$ determined at the last insertion ste...
Section 5.1.4: Tableaux and Involutions
Exercise 6. [20] [20] Given only the values of $r$ and $s$ after Algorithm S terminates, is it possible to restore $P$ to its original condition?
Verified: yes
Solve time: 1m17s
Solution
Let Algorithm S be the full sequence of insertions described in Algorithm I applied successively, terminating with a tableau $P$ and a final added position $(r,s)$ determined at the last insertion step, as in (8).
The data $(r,s)$ records only the location of the last created cell in the final tableau. It does not determine which element was inserted last, nor does it determine the preceding bumping sequence, hence it does not determine the previous tableau uniquely.
To prove non-recoverability, it suffices to exhibit two different initial inputs that produce different intermediate tableaux but yield the same final pair $(P,(r,s))$.
Consider the two permutations
$$ (1,3,2), \quad (2,3,1). $$
Apply Algorithm I step by step.
For $(1,3,2)$, inserting $1$ gives a single cell tableau. Inserting $3$ appends to the first row. Inserting $2$ bumps $3$ from row $1$ to row $2$, producing a final tableau
$$ P^{(A)} = \begin{array}{|c|c|} \hline 1 & 2\ \hline 3\ \hline \end{array} \quad \text{with final position } (r,s) = (2,1). $$
For $(2,3,1)$, inserting $2$ gives a single cell tableau. Inserting $3$ appends to the first row. Inserting $1$ bumps $2$ from row $1$ to row $2$, producing a final tableau
$$ P^{(B)} = \begin{array}{|c|c|} \hline 1 & 3\ \hline 2\ \hline \end{array} \quad \text{with the same final position } (r,s) = (2,1). $$
Both constructions yield the same values of $r$ and $s$, since in both cases the last insertion creates the new cell in row $2$, column $1$. However, the resulting tableaux satisfy
$$ P^{(A)} \ne P^{(B)}. $$
Since distinct intermediate tableaux arise from distinct insertion histories while the pair $(r,s)$ is identical, the mapping from final data $(P,(r,s))$ back to the original tableau before the last insertion is not uniquely determined by $(r,s)$ alone.
Therefore the original tableau $P$ cannot be restored from only the values of $r$ and $s$ after Algorithm S terminates.
This completes the proof. ∎