Another theatre line problem
 

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?

Re: Another theatre line problem
 

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

Re: Another theatre line problem
 

[ 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? [img]/images/graemlins/grin.gif[/img]

Re: Another theatre line problem
 

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

[/ QUOTE ]

Re: Another theatre line problem
 

Cute. My answer is below in white

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

Re: Another theatre line problem
 

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

Re: Another theatre line problem
 

<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>

Re: Another theatre line problem
 

[ 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

Re: Another theatre line problem
 

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

Re: Another theatre line problem
 

I think I've got it.

PairTheBoard

Re: Another theatre line problem
 

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

Re: Another theatre line problem
 

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

Re: Another theatre line problem
 

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.

Re: Another theatre line problem
 

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

Re: Another theatre line problem
 

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

PairTheBoard

Re: Another theatre line problem
 

[ 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!