2 ms·

I proved this in my college calc class - my proof was the shortest (one page) and it won me the textbooks for differential equations.

• drostie 13y ago
  It's actually a really easy bit of reasoning once you've got the "hang" of it. (sorry, bad pun.) Let the blocks have length 2 and look at the problem backwards: the topmost book's furthest-from-the-ledge edge is x=0, then x increases as we go towards the ledge. For the case of one block, the center of mass is clearly now at x=1 and that is the farthest away the ledge can be. We will have a function ledge(n) detailing the farthest the ledge can be as the number of books increases. The recursive rule is that when we place another book, the edge of the book must be where the ledge was -- any further and the books above must topple; any less far and the ledge is not the furthest out it could possibly be. So we just proved that the greedy algorithm is correct. ;-) The greedy algorithm then says that we lay out book n + 1 to have a center of mass at ledge(n) + 1, while the above n books had a center of mass at ledge(n). The combined center of mass is therefore: ledge(n + 1) = [n * ledge(n) + 1 * (ledge(n) + 1)] / (n + 1) = ledge(n) + 1/(n + 1) This recurrence relation from 1 generates the harmonic series, and so ledge(n) = H_n.