The Lowdown

N people are standing in a line, facing forward down the line. How many of them, on average, are able to say, “I am taller than everyone in front of me.” ?

##### About Kinetic Lowdown (33 Articles)
A Blog of All-Inclusive Interests & Oddities: Sharing Unique Information & Taboo Discussion

1. All of them ? Sorry I’m just guessing 😂

Liked by 1 person

2. N-1 people? Since they can all say it apart from the first person.

Like

• Thanks for commenting! It’s a really tricky one. Here’s the answer 🙂

Solution

First solution: Let TN be the expected number of people who are able to make
the given statement. If we consider everyone except the last person in line, then
this group of N − 1 people has by definition TN−1 people who are able to make the
statement. Let us now add on the last person. There is a 1/N chance that she is
the tallest, in which case she is able to make the statement. Otherwise she cannot.
Therefore, we have
TN = TN−1 +
1
N
. (1)
Starting with T1 = 1, we therefore inductively find
TN = 1 +
1
2
+
1
3
+ · · · +
1
N
. (2)
For large N, this goes like ln N, which grows very slowly with N.
Second solution: Let TN be the desired average. Consider the location of the
tallest person. If he is the last person in the line (which occurs with probability
1/N), then the problem reduces to that for the N − 1 people in front of him. So in
this case, we can expect 1 +TN−1 people who are able to make the given statement.
If the tallest person is the second to last person in the line (which occurs with
probability 1/N), then the problem reduces to that for the N − 2 people in front of
him (because the person behind him is not able to make the statement). So in this
case, we can expect 1 + TN−2 people who are able to make the given statement.
Continuing along these lines, and adding up all N possibilities for the location
of the tallest person, we find
TN =
1
N
³
(1 + TN−1) + (1 + TN−2) + · · · + (1 + T1) + (1 + T0)
´
=⇒ NTN = N + TN−1 + TN−2 + · · · + T1. (3)
Writing down the analogous equation for N − 1,
(N − 1)TN−1 = (N − 1) + TN−2 + TN−2 + · · · + T1, (4)
and then subtracting this from eq. (3), yields
TN = TN−1 +
1
N
, (5)
which agrees with the first solution.

Like

3. Can you solve the problem?

a) I give you an envelope containing a certain amount of money, and you open it. I then put into a second envelope either twice this amount or half this amount, with a fifty-fifty chance of each. You are given the opportunity to trade envelopes. Should you?

(b) I put two sealed envelopes on a table. One contains twice as much money as the other. You pick an envelope and open it. You are then given the opportunity to trade envelopes. Should you?

(c) If your answers to (a) and (b) are the same, explain why. If they are different, explain why.

Like