NZMO Round One

Solution:

We will show that the answer is $\binom{n}{2} = \frac{n(n - 1)}{2}$.
To show that this is sufficient, we will use induction.

- Base Case: Note that when $n = 1$, the two rows of numbers must be the same since there is only one permutation of $\{1\}$. Hence this case takes $0 = \binom{1}{2}$ turns.

- Inductive Step: Suppose that we know that it takes $\binom{n-1}{2}$ moves for two permutations of $\{1,2,\ldots,n-1\}$. Now consider two permutations of $\{1,2,\ldots,n\}$. We will show that it takes at most $n-1$ moves to put the number $n$ into the correct position.

Suppose that $n$ is in the $i$-th position in the first row, and that the $i$-th number in the second row is occupied by $k$. We first swap the positions of $k$ and $k + 1$, meaning that the $i$-th number in the second row is now $k + 1$. By repeating this argument with $k + 1$ and $k + 2$, $k + 2$ and $k + 3$, ..., $n - 1$ and $n$, we will have $n$ in the correct position. This takes $n - k$ moves, and since $1 \leq k \leq n$, the whole process takes at most $n - 1$ moves.

Once we have put $n$ into the correct position, we can effectively remove the $n$ from both rows, since we are able to arrange the rest of the numbers without touching $n$ again, showing that the problem has now been reduced to the $n - 1$ case. By the inductive hypothesis, the rest of the problem takes at most $\binom{n-1}{2}$ moves.

Hence, the maximum number of moves required is $\binom{n-1}{2}+n-1=\binom{n}{2}$.

To show that $\binom{n}{2}$ moves are necessary, we note that the Mad Hatter can write to force Alice to use $\binom{n-2}{2}$ moves. To show this, we define the warp of a permutation as follows: for each number in the permutation, its distance is the number of numbers to right of it which are smaller than itself. Then the warp is the sum of the distances over all the numbers in the permutation.

Note that on each move, the warp of a permutation either increases by 1 or decreases by one. This is because, if we swap the positions of $a$ and $a + 1$, then the only distance that can change is the distance of $a + 1$, and this may only increase by 1 (if $a + 1$ started on the right) or decrease by 1 (if $a + 1$ started on the left).

Now, since the warp of the first row at the start is $(n - 1) + (n - 2) + \dots +1 = \binom{n}{2}$, and the warp of the second row at the start is 0, the minimum number of moves required to turn the permutation $n, n - 1, \ldots, 1$ into the permutation $1, 2, \ldots, n$ is $\binom{n}{2}$.

We have thus proven that the answer is $\binom{n}{2}$.