Concerning the bookshelf problem

Original · EN

We discuss the following folklore problem. On a bookshelf, there are N tomes of the Encyclopedia in random order. Each hour, a librarian takes a tome which stands not on its place, and puts it in its place. Show that the process will stop. A natural additional question is how many moves are required for the process to stop. We show that the process can last 2ⁿ⁻¹-1 moves, and that it will stop anyway in less than 2ⁿ moves.