Problem 1332

Solution:

Antwort: Anaëlle hat $2^{n}$ Möglichkeiten.

Lösung 1 (bijektiv): Für jede ungerade ganze Zahl $1 \leq t < 2 n$, nenne die Menge aller Steine, deren Beschriftung die Form $t \cdot 2^{k}$ hat, die Kette ab $t$. Sobald wir einen Stein aus einer Kette in eine Schachtel platzieren, dann ist wegen der Bedingung die Schachtel aller anderen Steine in dieser Kette eindeutig bestimmt. Da $t$ ungerade ist, haben wir ausserdem, dass Steine in verschiedenen Ketten unabhängig voneinander platziert werden können, da die Bedingung nur Paare von Steinen betrifft, die in der selben Kette sind.
Weil jeder Stein zudem in genau einer Kette ist, folgt nun, dass jede erlaubte Verteilung der Steine eine entsprechende beliebige Verteilung von jeweils einem Stellvertretenden pro Kette hat (z.B. alle Steine mit ungerader Beschriftung). Weil wir $n$ Ketten haben, ist die gesamte Anzahl Möglichkeiten demnach $2^{n}$.

Lösung 2 (induktiv): Wir geben einen Induktionsbeweis. Die Antwort ist korrekt für $n=1$, da die beiden Steine (mit Beschriftung $1$ und $2$) in verschiedenen Schachteln platziert werden müssen. Betrachte nun den Fall mit $n>1$ und nehme an, die Antwort ist korrekt für alle kleineren Werte von $n$.
Es folgt, dass Anaëlle $2^{n-1}$ Möglichkeiten hat, um die Steine mit Beschriftung $1,2, \ldots, 2 n-2$ zu verteilen. Der Stein mit Beschriftung $2 n-1$ ist von keiner Bedingung eingeschränkt und kann daher in einer beliebigen Schachtel platziert werden. Für den Stein mit Beschriftung $2 n$ hat Anaëlle jedoch keine Wahl, da er nicht in der selben Schachtel wie der Stein mit Beschriftung $n$ platziert werden darf, welcher bereits platziert wurde (weil $n \leq 2 n-2$). Insgesamt hat Anaëlle also $2 \cdot 2^{n-1} = 2^{n}$ Möglichkeiten.