Maths Olympiad Prep

Library / /75 of 82

Combinatorics Difficulty 6.8 National olympiad Prove it Croatia

A hundred quadratic envelopes, each of different size, are arranged in a way that, for every two different envelopes, the smaller one is either inside of the bigger one, or they are outside of each other. At the same time, in both of the envelopes there can be other envelopes. Two arrangements are considered different if there are two envelopes which are inside each other in one of the arrangements, while being outside of each other in the other arrangement.
How many different arrangements are there such that the biggest envelope contains all the remaining envelopes? (Richard Stanley's problem set)

Solution

Denote the number of arrangements of nn envelopes as KnK_n.
Assume we are given an arrangement of nn envelopes. If we remove the smallest envelope, we obtain a possible arrangement of n1n-1 remaining envelopes. On the other hand, if we are given a possible arrangement of the remaining n1n-1 envelopes, we can put the smallest one directly in the biggest one, or in any of the remaining n2n-2 envelopes. Therefore, KnK_n is exactly n1n-1 times larger than Kn1K_{n-1}.
We conclude that Kn=(n1)Kn1==(n1)(n2)2K2K_n = (n-1) \cdot K_{n-1} = \cdots = (n-1) \cdot (n-2) \cdots 2 \cdot K_2.
For n=2n=2, the only possible arrangement is putting the smaller envelope inside the larger one, so K2=1K_2=1. Therefore Kn=(n1)(n2)1K_n = (n-1) \cdot (n-2) \cdots 1.
For 100 envelopes, the number of different arrangements is
K100=99981=99! K_{100} = 99 \cdot 98 \cdots 1 = 99!

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.