All Lined Up

A month between posts, thats about right. I guess I should post more frequently for the next little while, as I have learned a few new puzzles from Ben as of late, but we will see if that actually gets me to post more.

Anyway, time for the solution to the lineup puzzle that I posted last time.

So, its not hard to work out what the solution is for a few simple N, but it might be a bit tricky to see what the pattern is if you don't recognise it. For some small N values, the solution F(N) is given by:
F(1)=1
F(2)=3/2
F(3)=11/6
F(4)=25/12
F(5)=137/60

Gets sort of ugly, but if you take the differences:
F(2)-F(1)=1/2
F(3)-F(2)=1/3
F(4)-F(3)=1/4
F(5)-F(4)=1/5

The solution being the sum of 1/k from 1 to N seems like the obvious solution. You can go ahead and prove it by induction if you like, but there is a much cleaner solution.

Consider the people enter the lineup into random positions, starting with the tallest person. You can see the tallest person with probability 1, and shorter people added to the lineup cannot change that. You can see the second tallest person with probability 1/2, and shorter people added to the line cannot change that, you can see the kth tallest person with proably 1/k, and shorter people added to the lineup cannot change that. This gives the solution of the sum of 1/k (also known as the harmonic numbers).