Another theatre line problem

[BruceZ]

10 people stand in a single file line in front of a ticket window. The 10 people have 10 different heights. The ticket clerk can see a person if and only if no one taller stands in front of that person. How many people can the ticket clerk see on average?

[SheetWise]

<font color="white">4 (I get 4.5)</font>

[zerosum]

[ QUOTE ]
10 people stand in a single file line in front of a ticket window. The 10 people have 10 different heights. The ticket clerk can see a person if and only if no one taller stands in front of that person. How many people can the ticket clerk see on average?

[/ QUOTE ]

Do patrons wearing hats count? /images/graemlins/grin.gif

[BruceZ]

[ QUOTE ]
The ticket clerk can see a person if and only if no one taller stands in front of that person.

[/ QUOTE ]

[irchans]

Cute. My answer is below in white

<font color="white"> 2.93 on average </font>

[kyro]

<font color="white"> I haven't done the math yet, but my instinct tells me it is lower than this</font>

[bobman0330]

<font color="white"> The answer seems like it should be the 10th partial sum of the harmonic series.
The ticket taker can always see the first in line. There's a probability of .5 that the second person will be taller than the first. There's a probability of 1/3 that the third person will be taller than either of the first two, etc., etc.
1+1/2 + 1/3 + 1/4 + ... +1/10 = 2.929 </font>

[PairTheBoard]

[ QUOTE ]
10 people stand in a single file line in front of a ticket window. The 10 people have 10 different heights. The ticket clerk can see a person if and only if no one taller stands in front of that person. How many people can the ticket clerk see on average?

[/ QUOTE ]

Begin Aborted Attempt
<font color="white">
There are 10! ways they can line up.

First arrange them in order 1,2...,9,10 to see all 10. One way to do this.

Number of ways to see exactly 9:
Choose any of the first 9 and move him back one or more places. So, 9+8+7+6+5+4+3+2+1 = 9(9+1)/2 = 45

Number of ways to see exactly 8:
Choose any two of the first 9 and move them back one or more places.

Yikes. There's got to be an easier way.
</font>
End Aborted Attempt

PairTheBoard

[KenProspero]

LOL, I started down the same way, and came to the same conclusion

[PairTheBoard]

I think I've got it.

PairTheBoard

[PairTheBoard]

Begin; I think I've got it Solution
<font color="white">
This is another nifty application of the Sum of Expected Values that Bruce has shown us before.

Let the 10 people be in order of height, A1,A2,...,A10 with A1 the shortest and A10 the tallest.

For k=1...10 define the random variables Ik by:

Ik = 1 if Ak can be seen.
Ik = 0 if Ak cannot be seen.

Let N be the number of people in line that can be seen. We want to know E[N]. By the definitions,

N=I1+I2+...+In

So, E[N]=E[I1]+...+E[I10]

But E[Ik]=P[Ik=1] which we can calculate for each k.

P[I1=1] = 1/10
P[I2=1] = 1/10 + (1/10)(1/9)
P[I3=1] = 1/10 + (1/10)(2/9) + (1/10)(C(2,2)/C(9,2))
P[I4=1] = 1/10 + (1/10)(3/9) + (1/10)(C(3,2)/C(9,2)) + (1/10)(C(3,3)/C(9,3))
P[I5=1] = 1/10 + (1/10)(4/9) + (1/10)(C(4,2)/C(9,2)) + (1/10)(C(4,3)/C(9,3)) + (1/10)(C(4,4)/C(9,4))
...
P[I10=1] = 1/10 + (1/10)(9/9) + (1/10)(C(9,2)/C(9,2)) + ... + (1/10)(C(9,8)/C(9,8)) + (1/10)(C(9,9)/C(9,9))

Summing these as expectations and rearranging terms we get
E[I1]+...+E[I10] =
(1/10)10 +
(1/10)[(1+2+3+...+9)/9] +
(1/10)[C(2,2)+C(3,2)+...+C(9,2)]/C(9,2) +
(1/10)[C(3,3)+C(4,3)+...+C(9,3)]/C(9,3) +
(1/10)[C(4,4)+...+C(9,4)]/C(9,4) +
... +
(1/10)[C(8,8)+C(9,8)]/C(9,8) +
(1/10)C(9,9)/C(9,9)

= (1/10)(10 + 5 + 3.4 + 2.5 + 2 + 1.7 + 1.4 + 1.2 + 1.0 + 1)

= (1/10)(29.2)

or about 2.9 people.

</font>
End; I think I've got it Solution

Seems kind of small. Oh well.


PairTheBoard

[PairTheBoard]

Wow. Bobman's solution is so much nicer.
White
<font color="white">
Let Ik = 1 if the kth person in line can be seen.
</font>
End White

PairTheBoard

[BritNewbie]

I've no idea how to 'do it' exactly, so I tried a little simulation in Excel. Just thought it'd be interesting to compare my results with the numbers the mathematicians are coming up with.

Using a million simulations (actually, twenty simulations, each of fifty thousand queues) I got an average visible patrons of 2.928935.

Yeah, I know - small sample size.

Thanks to OP - interesting puzzle.

[RocketManJames]

Ok, I think I went about this the hard way and had to look up a sequence to get the answer.

So I computed the answers for N = 1, 2, 3, and 4.

N = 1, I got 1 / 1.
N = 2, I got 3 / 2.
N = 3, I got 11 / 6.
N = 4, I got 50 / 24.

So I have the denominators as factorials, and the numerator was this sequence that I didn't know off the top of my head. So, I looked up the sequence 1, 3, 11, 50. And I found that this is the sequence of Stirling Numbers (of the 1st kind)... some important combinatorial sequence that I vaguely learning a little bit about years ago.

So, I looked up the 10th Stirling number (indexed from 1), which was 10628640. And, 10! = 3628800.

So, we have 10628640 / 3628800 = 2.929.

-RMJ

[PairTheBoard]

That is truly a Stirling solution. Kind of amazing too.

PairTheBoard

[MickeyHoldem]

[ QUOTE ]
Ok, I think I went about this the hard way and had to look up a sequence to get the answer.

So I computed the answers for N = 1, 2, 3, and 4.

N = 1, I got 1 / 1.
N = 2, I got 3 / 2.
N = 3, I got 11 / 6.
N = 4, I got 50 / 24.

So I have the denominators as factorials, and the numerator was this sequence that I didn't know off the top of my head. So, I looked up the sequence 1, 3, 11, 50. And I found that this is the sequence of Stirling Numbers (of the 1st kind)... some important combinatorial sequence that I vaguely learning a little bit about years ago.

So, I looked up the 10th Stirling number (indexed from 1), which was 10628640. And, 10! = 3628800.

So, we have 10628640 / 3628800 = 2.929.

-RMJ

[/ QUOTE ]

I went the same way as you.... I had never heard of Stirling numbers. I went to N=5 for 274/120 and then found the relationship with the Harmonic series when I was trying to figure out the numerators. The numerator (Stirling Number) is just Harmonic Number(n) * n!