In The Line

Time for a new puzzle. I first found this one on the internets:
N people are standing in a lineup. There is a person at the front of the line (who is not one of the N) who can look down the line and see a given person if nobody taller than that person is in front of them. Each person in the line is of a unique height. What is the expected number of people that the person in front can see if each permutation of people is equally likely?

Just to make sure the wording is clear, with N=3, there are 6 cases (and assuming the line starts on the left and the person I name 1 is shortest and 3 is tallest):
123 -> three are visible
132 -> two are visible
213 -> two are visible
231 -> two are visible
312 -> one is visible
321 -> one is visible

So, on average, 11/6 people are visible in the N=3 case.

1 comment:

ed said...

Nice puzzle. The answer:

http://en.wikipedia.org/wiki/Harmonic_number