Suppose you have $n>1$ books lined up on a shelf, numbered $1$ to $n$, not in the correct order, and you wish to put them in order. Here's your method: Choose a misplaced book<sup>[1]</sup> at random, and put it in its correct spot. For example, if $n=5$ and you pick book number $2$ out of spot number $4$, there are now four books left, and you put the book back between the first two, since it's book number $2$.
What's the _maximum_ number of times you might have to do the pick-and-replace before the books are in order?
---
<sup>[1] meaning, a book numbered $k$ which is not in position $k$</sup>
msh210
·
2022-09-12T15:36:11Z (over 1 year ago)