A PuzzleCritic Original:
An empty 6-by-6 grid of squares is filled with numbers as follows. The first row contains the numbers {1,2,3,4,5,6} in some order. In each subsequent row, the kth number is equal to the position of the number k in the row above. For how many such grids are the first and last rows identical?
If you play around with a few examples, something strange seems to happen. Here is the grid whose first row is 463521:
4 6 3 5 2 1
6 5 3 1 4 2
4 6 3 5 2 1
6 5 3 1 4 2
4 6 3 5 2 1
6 5 3 1 4 2
We find that the odd rows are identical and the even rows are identical.
How about a first row of 542613?
5 4 2 6 1 3
5 3 6 2 1 4
5 4 2 6 1 3
5 3 6 2 1 4
5 4 2 6 1 3
5 3 6 2 1 4
Again the top two rows are just repeated.
What about a first row of 132654?
1 3 2 6 5 4
1 3 2 6 5 4
1 3 2 6 5 4
1 3 2 6 5 4
1 3 2 6 5 4
1 3 2 6 5 4
Here we find that every row is the same!
What is really going on? Suppose that in some row of the grid, the number x is in position y? Then in the next row, the number y will be in position x, and in the following row, the number x will again be in position y.
For example, say the number 4 is in the 2nd position in row 1. Then in row 2, the 4th entry will be the position of the number 4 in the previous row, namely 2; so the number 2 will be in the 4th position. Similarly, it follows that in row 3, the number 4 will be in the 2nd position, just like it was in row 1.
Hence every other row of the grid is identical, and in order for the first and last rows to be the same, we just require the first two rows to be the same. For this, we need the following to be true for all x and y in row 1:
If x is in position y then y is in position x.
This condition is obviously satisfied if any number occupies its natural position, for example if 3 is in the 3rd position. Otherwise, the numbers must pair up; for example, if 1 is in the 4th position, then 4 must be in the 1st position. Since there are only six numbers in a row, we can have either 0, 1, 2 or 3 of these ‘transpositions’. We investigate each case separately:
0 transpositions
This means every number in row 1 occupies its natural position, that is, row 1 is 123456. So there is just 1 possible first row containing 0 transpositions.
1 transposition
Examples include 123654 (with 4 and 6 swapped) and 213456 (with 1 and 2 swapped). In total, there are 15 such rows, one for each pair of numbers from 1 to 6.
2 transpositions
Examples include 165432 (2 swapped with 6, 3 swapped with 5) and 423165 (1 swapped with 4, 5 swapped with 6). We have 15 ways to choose the two numbers that are fixed, and for each of these we have 3 ways to pair up the other four numbers. So there are 45 rows containing two transpositions.
3 transpositions
Examples include 532614 (1 swapped with 5, 2 swapped with 3, 4 swapped with 6) and 654321 (1 swapped with 6, 2 swapped with 5, 3 swapped with 4). Here we have 5 choices for the number paired up with 1, and for each of these we have 3 ways to pair up the other 4 numbers. So there are 15 rows containing 3 transpositions.
Thus in total there are 1+15+45+15=76 different ways to choose the first row, after which the rest of the grid is uniquely determined (every row will be identical to row 1). Therefore the final answer is 76.