A two year old has 8 plastic cups of different sizes that can be put inside each other.

probability/nesting.cups New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

A two year old has 8 plastic cups of different sizes that can be put
inside each other.  (Each cup is cylindrical with bottom, but no top.)
With all cups spread out on the floor he tries to put them together
using the following "rules":

1. He grabs a random cup not yet mounted.
2. If possible, he mounts it bottom down. If not he tries to mount it
   bottom up. If this is impossible too he loses.
3. If more cups go to step 1, else he succeeds.

He is never allowed to touch the cups already mounted, and no cups
shall be put on top of another (forming a tower), only inside, i.e.
covering the smaller ones.  The final object shall be of same size as
the largest cup.

What is the probability of success?

Show solution

Look at the final configurations which represent success. Each cup
can be mounted in either the up or down position. Hence there are
exactly 2^8 such configurations. Note however that the smallest cup
will only ever appear facing up, since if it can be fitted at all, it
can always be fitted face up. Thus we are reduced to 2^7 finishing
configurations.

We now check that each of these 2^7 configurations can result from
choosing the cups in exactly one order.  In fact you can reconstruct
the order that the cups were selected in by looking at the configuration.

For example, if the largest cup is cup 8 and the smallest cup is cup 1,
then the finishing configuration which has cups 2, 4, 5, and 7 facing
down and all other cups facing up must have been obtained as follows

Start at the smallest cup and work up.                  1
Since cup 2 is face down it was chosen
        after cup 1                                     12
Since cup 3 is face up it was chosen
        before cups 1 and 2 which fit inside it         312
As cup 4 is face down it was chosen after
        cups 1, 2, and 3 which it covers                3124
Cup 5 is face down so chosen after                      31245
Cup 6 is face up so chosen before                       631245
Cup 7 is face down so chosen after                      6312457
Cup 8 is face up so chosen before                       86312457

By examining the example we see that we have an algorithm for determining
the unique order that the cups must have been chosen in to reach each of
the 2^7 finishing configurations. Notice how the sizes of the selected cups
first steadily decrease then steadily increase. This is an essential
property for success. Another way to solve the puzzle would be to count
all sequences of this type.

Thus of the 8! ways that the cups can be randomly selected, 2^7 of them
will result in success, and the rest will result in failure. As each order
is equally likely, the probability of success is

P(success) = 2^7 / 8! or approximately 0.003174603

I hope your son is very patient. He will succeed only three times in every
thousand attempts. :-)

-- Ian H <hawthorn@waikato.ac.nz>

[ Editor: the problem was posed by Jon Haugsand <jonhaug@ifi.uio.no>. ]