Kanada, 2012

Combinatorics Difficulty 6.5 National Olympiad Prove it Canada

A bookshelf contains $n$ volumes, labelled $1$ to $n$ in some order. The librarian wishes to put them in the correct order as follows. The librarian selects a volume that is too far to the right, say the volume with label $k$ , takes it out, and inserts it so that it is in the $k$ -th place. For example, if the bookshelf contains the volumes $1$ , $3$ , $2$ , $4$ in that order, the librarian could take out volume $2$ and place it in the second position. The books will then be in the correct order $1$ , $2$ , $3$ , $4$ .

a. Show that if this process is repeated, then, however the librarian makes the selections, all the volumes will eventually be in the correct order.

b. What is the largest number of steps that this process can take?

Une étagère contient $n$ volumes étiquetés de $1$ à $n$ , rangés dans un certain ordre. Le bibliothécaire souhaite les mettre dans le bon ordre de la façon suivante : il choisit un volume qui se trouve trop à droite, par exemple le volume étiqueté $k$ , le retire de son emplacement et l'insère à la $k$ -ième place. Par exemple, si les volumes sont rangés dans l'ordre $1$ , $3$ , $2$ , $4$ , le bibliothécaire peut prendre le volume $2$ et le mettre à la deuxième place. Les livres sont alors rangés dans le bon ordre, soit $1$ , $2$ , $3$ , $4$ .

a) Démontrez que si l'on répète ce processus, tous les volumes finiront par être dans le bon ordre, et ce, quelle que soit la manière dont le bibliothécaire les range.

b) Quel est le plus grand nombre d'étapes que peut exiger un tel processus?

Solution

(a) If $t_k$ is the number of times that volume $k$ is selected, then we have $t_k \le 1 + (t_1 + t_2 + \dots + t_{k-1})$ . This is because volume $k$ must move to the right between selections, which means some volume was placed to its left. The only way that can happen is if a lower-numbered volume was selected. This leads to the bound $t_k \le 2^{k-1}$ . Furthermore, $t_n = 0$ since the $n$ th volume will never be too far to the right. Therefore if $N$ is the total number of moves then
$N = t_1 + t_2 + \dots + t_{n-1} \le 1 + 2 + \dots + 2^{n-2} = 2^{n-1} - 1,$

and in particular the process terminates.

(b) Conversely, $2^{n-1}-1$ moves are required for the configuration $(n, 1, 2, 3, \ldots, n-1)$ if the librarian picks the rightmost eligible volume each time.
This can be proved by induction: if at a certain stage we are at $(x, n-k, n-k+1, \ldots, n-1)$ , then after $2^k-1$ moves, we will have moved to $(n-k, n-k+1, \ldots, n-1, x)$ without touching any of the volumes further to the left. Indeed, after $2^{k-1}-1$ moves, we get to $(x, n-k+1, n-k+2, \ldots, n-1, n-k)$ , which becomes $(n-k, x, n-k+1, n-k+2, \ldots, n-1)$ after 1 more move, and then $(n-k, n-k+1, \ldots, n-1, x)$ after another $2^{k-1}-1$ moves. The result follows by taking $k=n-1$ .

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

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