## Task 3B - 301233B

Let $D_{1}, \ldots, D_{n}$ be cans, for whose sizes (diameters) $d_{1}, \ldots, d_{n}$ in a suitable unit of measurement

$$
d_{1}=2, \quad d_{2}=3, \quad \ldots, \quad d_{n}=n+1
$$

holds. Furthermore, let $G_{1}, \ldots, G_{n}$ be objects, for whose sizes $g_{1}, \ldots, g_{n}$

$$
g_{1}=1, \quad g_{2}=2, \quad \ldots, \quad g_{n}=n
$$

holds. The sizes are adjusted such that the following holds:

$G_{i}$ fits into $D_{j}$ if and only if $g_{i} \leq d_{j}$.

Determine for each natural number $n \geq 1$ the number $A(n)$ of all distributions of the objects into the cans, where exactly one object is in each can.

Hint: Two distributions are called different from each other if and only if at least one object is in a different can in one of these two distributions compared to the other distribution.
First, we observe that for \( n \geq 2 \), the object \( G_{n} \) must be placed in one of the two boxes \( D_{n-1} \) or \( D_{n} \). In both cases, all other objects fit into the other of the two boxes just mentioned.

Thus, for \( n \geq 2 \), every distribution of the objects \( G_{1} \) to \( G_{n} \) into the boxes \( D_{1} \) to \( D_{n} \) can be obtained by modifying a distribution of the objects \( G_{1} \) to \( G_{n-1} \) into the boxes \( D_{1} \) to \( D_{n-1} \) in one of the following two ways:

a) Simply add the object \( G_{n} \) to the still empty box \( D_{n} \).

b) Remove the object currently in box \( D_{n-1} \), place it in the previously empty box \( D_{n} \), and place the object \( G_{n} \) in the now empty box \( D_{n-1} \).

Clearly, both variants lead to different distributions, and any two initial distributions of the first \( n-1 \) objects into the first \( n-1 \) boxes also result in different distributions, as at least two boxes are filled differently in each case.

Therefore, for every \( n \geq 1 \), the recursion \( A(n+1) = 2 A(n) \) holds. Together with \( A(1) = 1 \), it follows that \( A(n) = 2^{n-1} \).