Question 30
Consider an $n\times n$ grid filled with the numbers $1,\ldots,n^2$ in ascending order from left to right, top to bottom. A shuffle consists of the following two steps:
- Shift every entry one position to the right. An entry at the end of a row moves to the beginning of the next row and the bottom-right entry moves to the top-left position.
- Then shift every entry down one position. An entry at the bottom of a column moves to the top of the next column and again the bottom-right entry moves to the top-left position.
An example for the $3\times3$ grid is shown. Note that the two steps shown constitute one shuffle.
What is the smallest value of $n$ for which the $n\times n$ grid requires more than 20000 shuffles for the numbers to be returned to their original order?
- Shift every entry one position to the right. An entry at the end of a row moves to the beginning of the next row and the bottom-right entry moves to the top-left position.
- Then shift every entry down one position. An entry at the bottom of a column moves to the top of the next column and again the bottom-right entry moves to the top-left position.
An example for the $3\times3$ grid is shown. Note that the two steps shown constitute one shuffle.
What is the smallest value of $n$ for which the $n\times n$ grid requires more than 20000 shuffles for the numbers to be returned to their original order?