## January 2010 riddle

This month's riddle was suggested by Oded Margalit.

Answer either or both parts. Separate solvers' lists will be kept for each part.

#### Part 1:

Larry the Librarian is faced with the task of sorting the volumes of a multi-volume encyclopedia. The encyclopedia contains n volumes and fits entirely on a single shelf. His objective is to sort the volumes by their order, placing volume 1 as the left-most volume, volume 2 as the next, etc., until volume n, which will be the right-most volume on the shelf.

For reasons that will remain between Larry and his employer, Larry's objective is to perform this task so that it will take the greatest amount of time.

The strategy he has opted for is as follows: in the beginning of each day, he looks through the volumes until he finds one that is too far to the right. A volume that is too far to the right is simply a volume whose number is x and which is currently in the y'th position from the left on the shelf, with x<y. Notably, Larry does not have to pick the volume by lowest x or lowest y or any other criterion. Any volume that is too far to the right will do.

Once Larry has chosen a volume, he picks it up from its current position on the shelf and brings it to its correct position (the x'th position from the left), pushing the rest of the volumes to the side in order to make space for it.

Larry repeats this procedure once a day, until the encyclopedia volumes are all sorted.

The question: prove that this strategy does, indeed, eventually result in all volumes of the encyclopedia reaching their sorted order. Find the maximal number of days that Larry may need in order to complete the sort (from the unsorted arrangement that maximizes this number).

#### Part 2:

Laura the Librarian has a similar dilemma to that faced by Larry. The only difference is that Laura decided on a slightly different tactic. Whereas Larry can only choose a volume that is too far to the right, Laura allows herself to choose each day one of the volumes that is out of place, regardless of whether it is too far to the right or too far to the left.

The question: does Laura's strategy still guarantee that the volumes will, eventually, be sorted?

All answers should be accompanied by proofs.

### List of solvers:

#### Part 1:

Omer Angel (1 January 15:26)
Itsik Horovitz (2 January 10:02)
Sen Gu (4 January 00:54)
Øyvind Grotmol (5 January 19:49)
Dan Dima (6 January 22:02)
Hongcheng Zhu (10 January 01:34)
Rani Hod (11 January 03:34)
Daniel Bitin (13 January 02:12)
Phil Muhm (13 January 09:10)
Slobodan Mitrović (15 January 13:38)
Li Wei (16 January 17:35)
Shmuel Menachem Spiegel (18 January 14:58)
Bojan Bašić (23 January 05:43)
Ante Turudić (24 January 23:07)

#### Part 2:

Omer Angel (1 January 15:26)
Itsik Horovitz (2 January 10:02)
Øyvind Grotmol (6 January 04:49)
Hongcheng Zhu (10 January 21:14)
Daniel Bitin (15 January 04:59)
Li Wei (15 January 16:39)
Bojan Bašić (23 January 05:43)
Ante Turudić (24 January 23:07)
Slobodan Mitrović (26 January 10:13)
Phil Muhm (27 January 09:18)

Elegant and original solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!