Library / /1369 of 1394

, 2018

Combinatorics Difficulty 6.3 National Olympiad Prove it United States

Problem:
A tourist is learning an incorrect way to sort a permutation $\left(p_{1}, \ldots, p_{n}\right)$ of the integers $(1, \ldots, n)$ . We define a fix on two adjacent elements $p_{i}$ and $p_{i+1}$ , to be an operation which swaps the two elements if $p_{i}>p_{i+1}$ , and does nothing otherwise. The tourist performs $n-1$ rounds of fixes, numbered $a=1,2, \ldots, n-1$ . In round $a$ of fixes, the tourist fixes $p_{a}$ and $p_{a+1}$ , then $p_{a+1}$ and $p_{a+2}$ , and so on, up to $p_{n-1}$ and $p_{n}$ . In this process, there are $(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}$ total fixes performed. How many permutations of $(1, \ldots, 2018)$ can the tourist start with to obtain $(1, \ldots, 2018)$ after performing these steps?

Solution

Solution:
Note that the given algorithm is very similar to the well-known Bubble Sort algorithm for sorting an array. The exception is that in the $i$ -th round through the array, the first $i-1$ pairs are not checked.

We claim a necessary and sufficient condition for the array to be sorted after the tourist's process is: for all $i$ , after $i$ rounds, the numbers $1, \cdots, i$ are in the correct position. Firstly, this is necessary because these indices of the array are not touched in future rounds - so if a number was incorrect, then it would stay incorrect. On the other hand, suppose this condition holds. Then, we can "add" the additional fixes during each round (of the first $i-1$ pairs during the $i$ -th round) to make the process identical to bubble sort. The tourist's final result won't change because by our assumption these swaps won't do anything. However, this process is now identical to bubble sort, so the resulting array will be sorted. Thus, our condition is sufficient.

Now, there are two positions the $1$ can be in $\left(p_{1}, p_{2}\right)$ . There are three positions the $2$ can be in $\left(p_{1}, \cdots, p_{4}\right)$ except for the position of $1$ . Similarly, for $1 \leq i \leq 1009$ there are $2i-(i-1)=i+1$ positions $i$ can be in, and after that the remaining $1009$ numbers can be arranged arbitrarily. Thus, the answer is $1010! \cdot 1009!$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.