Question 89
Original English statement:
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?
Translation of the parallel French statement:
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?
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?
Translation of the parallel French statement:
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?