Library / Croatian Mathematical Competitions /100 of 114

Croatian Mathematical Competitions

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 $n$ envelopes as $K_n$ .
Assume we are given an arrangement of $n$ envelopes. If we remove the smallest envelope, we obtain a possible arrangement of $n-1$ remaining envelopes. On the other hand, if we are given a possible arrangement of the remaining $n-1$ envelopes, we can put the smallest one directly in the biggest one, or in any of the remaining $n-2$ envelopes. Therefore, $K_n$ is exactly $n-1$ times larger than $K_{n-1}$ .
We conclude that $K_n = (n-1) \cdot K_{n-1} = \cdots = (n-1) \cdot (n-2) \cdots 2 \cdot K_2$ .
For $n=2$ , the only possible arrangement is putting the smaller envelope inside the larger one, so $K_2=1$ . Therefore $K_n = (n-1) \cdot (n-2) \cdots 1$ .
For 100 envelopes, the number of different arrangements is
$K_{100} = 99 \cdot 98 \cdots 1 = 99!$

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.