Periscope Depth

no more pencils, no more books

The following problem kept me up about an hour past my bedtime on Sunday. I didn’t read it anywhere (that I recall); it came to me as a thought experiment. I’m stumped, so I’m crowdsourcing the solution.

POSIT: A math professor comes home one day to find that his 8-year-old son knocked over the bookcase in the study. The bookcase is wrecked and heavy math textbooks are everywhere. The professor grounds his son for two weeks.

laiva-bookcaseHe then buys a used bookshelf on Craigslist. Sadly, this bookshelf is a rickety IKEA reject. It can only hold n heavy math textbooks on any given shelf provided there are n+1 heavy math textbooks on the shelf beneath it. If a higher shelf has a number of books equal or greater than the shelf beneath it, the shelf will tip over. (This doesn’t hold true for the bottommost shelf)

The next day, the professor sets his grounded 8-year-old son to reshelve all his math textbooks. Bored at being stuck indoors, the 8-year-old decides to make a game out of this project. The game has the following rules.

(1) The boy can, in a single move, either shift a book from the floor to the bottommost shelf, or shift a book from one shelf to the shelf above it.
(2) The boy cannot shift more than one book at a time in a single move.

So he can shift a book from the (vast) pile on the floor to the bottommost shelf, or he can shift a book from a lower shelf to a higher one. But he cannot shift a book such that it’ll cause the shelf to tip over (i.e., leaving four books on one shelf and three on the one beneath it, or two books on adjacent shelves).

After some time of this, the boy finds himself with the following allocation:

Three books on the bottom (or 1st) shelf
Two books on the 2nd shelf
One book on the 3rd shelf*
… and an uncounted pile of books scattered on the floor.

QUESTIONS:

(1) How many moves will it take him to get one book on the 4th shelf?
(2) Is there a formula for determining the number of moves it would take to get a book onto the 4th shelf? Or onto any given shelf?

#2 is the more interesting question for me. I could work #1 out through brute force on Sunday, shuffling flat glass beads around as if they were books on a shelf. But I couldn’t figure out what the formula was.

If you’re good with the math, please take a stab at this. If you’re not, please forward it on to someone whom you think might like it. The solution’s not going to save a life or win the Clay Prize or anything. But I’m curious and it’s probably trivial to someone who knows more than me about math.

*I’m aware that this allocation couldn’t exist if the boy was following his own rules from the get-go. 8-year-olds are fickle.