ALL EN FR ES IT

Logo

≡ ► ◄ ▲

Undisziplinierte Gesellschaft

Mathematik Nr. 119

An einem drehbaren runden Tisch mit 12 Plätzen sind die Tischkärtchen für die erwarteten 12 Personen aufgestellt. Die Personen ignorieren aber die Kärtchen und verteilen sich zufällig auf die Plätze.

Ist es immer möglich mit einer einzigen Drehung des Tisches zu erreichen, dass mindestens zwei Personen vor ihren Tischkärtchen sitzen?

Lösung anzeigen

Ja, es ist möglich.

Die tatsächliche Sitzreihenfolge ist irgendeine Permutation P von {1,...,12}. Der Wert P(i)-i gibt nun an, wie weit man den Tisch drehen muss, damit die Person, die jetzt am i-ten Platz sitzt, vor dem richtigen Namensschild sitzt. Negative Werte bedeuten dabei eine Drehung in die andere Richtung als positive Werte. Diese Werte sind natürlich nur bis auf modulo 12 bestimmt, denn eine Drehung des Tisches um 8 (in eine Richtung) ist dasselbe wie eine Drehung um -4 (dadurch in die andere Richtung).

Die Aufgabe ist nun äquivalent damit zu fragen, ob es für jede Permutation P zwei verschiedene Indizes i und j gibt, sodass P(i)-i = P(j)-j gilt.

Angenommen bei einer Permutation P wäre das nicht der Fall, dann müssten alle 12 Werte P(1)-1, P(2)-2, ..., P(12)-12 verschieden sein. Da es aber genau 12 Restklassen modulo 12 gibt, müssten diese 12 Werte jede dieser 12 Restklassen genau einmal annehmen.

Summiert man diese 12 Differenzen P(1)-1, ... P(12)-12, so erhält man umgestellt die Summe aller P(1), P(2), ... P(12) und davon abgezogen die Summe aller 1, 2, ..., 12. Da P eine Permutation von {1,2,...,12} ist, sind diese Summen aber gleich, das heißt, die Differenz ist 0.

Andererseits ist diese Summe aber - wie gezeigt - auch gleichzeitig die Summer aller 12 Restklassen modulo 12, also 1+2+...+12 modulo 12 = 6 modulo 12. Das ist ein Widerspruch.