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.” ?

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.

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.

All of them ? Sorry I’m just guessing 😂

LikeLiked by 1 person

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

LikeLike

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.

LikeLike

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.

LikeLike