Problem 1774

Solution:

Nehme an, jedes Auto führt eine Fahne mit sich. Wenn sich zwei Autos begegnen, tauschen sie die Fahnen aus. Die Fahnen ändern also nie ihre Bewegungsrichtung und sind daher nach einer Stunde alle wieder an ihrem ursprünglichen Platz. Das bedeutet aber, dass auch die $n$ Autos wieder alle auf den Startpositionen stehen, aber eventuell permutiert. Sei $\pi$ diese Permutation. Jede weitere Stunde permutiert die Autos offenbar wieder in derselben Weise (die Fahrtrichtung an jedem der Startplätze ist dieselbe wie am Anfang), also ist die Platzvertauschung der Autos nach $k$ Runden gegeben durch die Permutation $\pi^{k}=\pi \circ \ldots \circ \pi$. Wir zeigen nun, dass eine Zahl $d$ existiert, sodass $\pi^{d}=\mathrm{id}$ die Identität ist. Dann befinden sich alle Autos nach $d$ Runden wieder auf ihrem Startplatz.

Betrachte dazu die Folge $\pi, \pi^{2}, \pi^{3}, \ldots$ Da es nur endlich viele Permutationen von $n$ Dingen gibt (nämlich $n!$ Stück), müssen zwei Glieder in dieser Folge übereinstimmen, das heisst, es gibt $i<j$ mit $\pi^{i}=\pi^{j}$. Da $\pi$ eine bijektive Abbildung ist, können wir diese Gleichung mit $\pi^{i}$ kürzen und erhalten $\pi^{j-i}=\mathrm{id}$, wie gewünscht.