A magic square is $2\times 4$ matrix with entries $1, 2, \dots, 7, 8$ where no entry occurs twice (equivalent to a permutation). As an example, consider the following magic square:
$\displaystyle \begin{bmatrix} 1 & 2 & 3 & 4 \\ 8 & 7 & 6 & 5 \end{bmatrix}$
There are three transformations that can be applied to a magic square, each an arbitrary number of times and the order doesn't matter:
- exchange the top and bottom row,
- single right circular shift of the matrix,
- single clockwise rotation (90 deg) of the $2\times 2$ submatrix in the middle (the submatrix with the entries $2,3,6,7$ in the example above).
Let's apply these transformations to the example above to illustrate what they do:
$\displaystyle 1: \begin{bmatrix}8 & 7 & 6 & 5 \\ 1 & 2 & 3 & 4\end{bmatrix} \qquad 2: \begin{bmatrix}4 & 1 & 2 & 3 \\ 5 & 8 & 7 & 6\end{bmatrix} \qquad 3: \begin{bmatrix}1 & 7 & 2 & 4 \\ 8 & 6 & 3 & 5\end{bmatrix}$
QUESTION. In the problem statement from IOI '96 one reads the following claim.
All possible configurations are available using the three basic transformations.
Why is that true?
Of course, since there are only $8! = 40320$ magic squares, a simple breadth-first search traversal will show the claim is true. But let's forget about the computer. Is there another way to prove the claim using a combinatorial observation? How can we show that every state is reachable?