On a bookshelf, there are N tomes of the encyclopedia in random order. Every hour, a librarian takes a tome which is not in place and puts it in its place, and we must show this process will stop eventually.
I managed to solve this question assuming that eventually the librarian will pick either the first or last tome and put it in its place (Then we can look at the books as N-1 books in random order, so we can use induction). However, since the tomes the librarian picks are random, I can't really assume that, so I'm stuck.
EDIT: To clear a misunderstanding, the librarian chooses a tome randomly from all the tomes not in place. Meaning, if he picks the first book, he will put it in its place and never touch it again. However, if the librarian picks the 3rd tome and puts in in its place (3rd book on the shelf), and then picks the 2nd book and puts in the 2nd spot on the shelf, the 3rd book will move to the 4th position, and this is making it tricky.
EDIT2: This is not swapping, it is insertion. The librarian picks a book i of N books, removes it to leave us with N-1 books on the shelf. Then, the book is placed in the ith spot on the shelf.
Here is a full proof, working off the idea of Ross Millikan.
First of all, let's define the error of volume number $k$ at place number $i$ to be the number $k-i$. In addition, call a book is positive, negative or neutral depending on the sign of its error.
As the librarian moves a book, the sum of the absolute value of the error of all the books either decreases or stays the same. If it decreases, then we are obviously closer to a sorted shelf, and if it ever becomes zero, then the shelf must be sorted. It remains to show that the number of moves the librarian has available before the total error has to decrease is bounded.
Partition the shelves into blocks the following way: A positive block is a contiguous set of books that are either positive or neutral, so that the first and last book in the block are positive, and the next non-neutral book on either side is negative (apart from the beginning and end of the shelf). Negative blocks are defined similarily, and neutral blocks are the contiguous blocks of neutral books that (might) lie between a positive and a negative block. See the picture below of a sample shelf of books, where the blue $\color{blue}{+}$ denotes a positive book, the red $\color{red}{-}$ signifies a negative book, and a gray $\color{gray}{0}$ signifies a neutral book. The blocks are designated as in the picture.
As the librarian moves a book with error $e$, that book gets error $0$, but there are $|e|$ books that have their error either increased by $1$ or decreased by $1$, depending on the sign of $e$ (the total sum of all the errors, including signs has to be $0$, this is not difficult to see). If the book was positive, and all the $|e|$ other books were either positive or neutral, then the sum of the absolute value of all the errors is unchanged. Same thing for negative. We therefore see that the absolute value sum of errors decrease if and only if a book is moved out of its block.
So we need to show that there is a bound to how many times the librarian can move books around until she has to take a book out of its block. Note that if a move takes a book from a block and places it at the edge of that same block, then that block will shrink in size by $1$ and the adjacent neutral block will increase in size by $1$ (possibly coming into existence). Even though the block in question has lost a book, I will still call it the same block.
Every time the librarian picks a book, she will pick one book in some block. Therefore, if every block has a bounded "lifespan", eventually she will have to pick a block where every available book will be moved outside the block. Therefore we can focus our attention to the lifespan of a single block.
Assume from here on out that we're in a negative block (positive blocks work just the same, only mirrored), and the orientation is as in the picture above, ascending left-to-right, as is the usual encyclopedia order orientation (this means positive books "wants" to go to the right, negative books wants to go left). Give that block points based on the books in it in the following way: The rightmost book (which must be negative) is worth $1$ point. The next one is worth $2$ points if it's negative. The third one is worth $4$ points if it's negative (no matter what the second book was), and so on, using powers of two all the way up to the last one, which is again guaranteed to be negative. Negative books are worth zero points.
For instance, the rightmost negative block in the picture has $1 + 2 + 0 + 8 + 16 = 27$ points, while the leftmost positive block has $1+2+0+8 = 11$ points (remember, positive blocks are mirrored).
A move within that block is guaranteed to lower the total sum of points. The easy way to explain this is that the points of the block represented in base-two will have ones and zeros in exactly the same pattern as the negative and neutral books in the shelf. As you move a book, that will flip a $1$ to a $0$ somewhere in that base-two number. It might mess up everything in the digits that are less significant, but it won't touch the ones that are more significant, and therefore we end up with a strictly smaller number.
Therefore, every move within a block takes you closer to a point where you have to take a book out of the block, and taking a book out of a block means the sum of absolute value of errors decrease. Therefore, at some point the shelf has to be sorted.