IMO-Aufgabe: Hässliche Dinge für immer loswerden

Von

Es gibt schöne Geschenke und solche, die man am liebsten gleich weiter verschenkt. Manch hässliches Präsent kann auf diese Weise über Umwege wieder zum ursprünglichen Verschenker gelangen. Mit einer Formel lässt sich dies verhindern.

Aufgabe:

Ein Club hat n Mitglieder. Die Mitglieder sind von 1 bis n durchnummeriert. Die Leute in dem Club machen sich gern untereinander Geschenke, allerdings sind darunter häufig auch Dinge, die sie einfach nur loswerden wollen. So kommt es immer wieder zu der peinlichen Situation, dass ein Mitglied geschenkt bekommt, was es zuvor selbst verschenkt hat.

Peep-Show der Gartenzwerge: Hässliches, du hast so was Verlässliches, dichtete eins Robert Gernhardt. Mathematiker wissen, wie man sich peinliche Geschenke vom Leibe hält
DPA

Peep-Show der Gartenzwerge: Hässliches, du hast so was Verlässliches, dichtete eins Robert Gernhardt. Mathematiker wissen, wie man sich peinliche Geschenke vom Leibe hält

Um dies zu verhindern, hat der Club eine Regel aufgestellt: Das Mitglied mit der Nummer a darf dem Mitglied mit der Nummer b nur dann etwas schenken, wenn das Produkt a*(b-1) durch n teilbar ist. Beweisen Sie, dass bei Beachtung dieser Regel Geschenke nie mehr zum ursprünglichen Verschenker zurückkommen können.

Lösung:

Ein erstes Gefühl für die Aufgabe kann man bekommen, wenn man beispielsweise den Fall n=6 untersucht, der Club also genau sechs Mitglieder hat. Mitglied a darf Mitglied b nur dann etwas schenken, wenn a*(b-1) durch 6 teilbar ist. Dies ist für folgende Paare (a,b) der Fall: (6,2), (6,3), (6,4), (6,5), (2,4) und (3,5). Das bedeutet: Nur die Clubmitglieder mit den Nummern 2, 3 und 6 dürfen überhaupt etwas verschenken - und zu diesen Mitgliedern kann kein Präsent zurückkommen, weil die Geschenkstaffetten spätestens bei der dritten Person enden - zum Beispiel 6->2->4 oder 6->3->5.

Gesucht ist allerdings eine Lösung für alle erdenklichen n. Der Beweis dafür wird indirekt geführt. Wir nehmen an, dass es eine Geschenkkette gibt, die von a1, a2, a3, … bis zu ak führt und von dort wieder zurück zu a1.

Weil die Clubregel für alle Produkte a*(b-1) zutreffen muss, gilt für alle i (i=1,…k):

ai*(ai+1-1) = ai*ai+1-ai ist durch n teilbar.

Dies kann man auch anders formulieren: ai*ai+1 und ai lassen bei der Division durch n den gleichen Rest (nur dann ist ihre Differenz durch n teilbar), oder wie der Mathematiker sagt: ai*ai+1 und ai sind kongruent modulo n.

Wenn man dies untereinander schreibt, erhält man:

a1 ist kongruent zu a1*a2
a2 ist kongruent zu a2*a3
a3 ist kongruent zu a3*a4
...
ak-1 ist kongruent zu ak-1*ak
ak ist kongruent zu ak*a1

Nun setzt man in die jeweils obere Kongruenz fortwährend in die darunter ein (dies darf man wegen der Kongruenz-Rechenregel zum Mulitplizieren):

a1 ist kongruent zu a1*a2*a3
a1 ist kongruent zu a1*a2*a3*a4
...
a1 ist kongruent zu a1*a2*a3*a4...*ak

Jetzt wird dieses Spielchen wiederholt, allerdings fängt man mit a2 ist kongruent a2*a3 an und setzt darin Schritt für Schritt die darunterliegenden und zum Schluss die oberste Gleichung ein. Das Ergebnis lautet:

a2 ist kongruent zu a1*a2*a3*a4...*ak

Dies wiederholt man nun für alle ai (i=1, 2,...k) und erhält:

ai ist kongruent zu a1*a2*a3*a4...*ak

Daraus folgt: Alle Zahlen ai lassen bei der Division durch n denselben Rest, nämlich den, den auch das Produkt a1*a2*a3*a4...*ak lässt. Das ist jedoch nicht möglich, schließlich sind ai alles paarweise verschiedene Zahlen aus dem Bereich 1, 2, …, n (ai sind ja sämtlich Mitgliedsnummern des Clubs!). Damit ist ein Widerspruch aufgetreten, die Annahme zu Beginn des Beweises kann deshalb nicht stimmen. Fazit: Es gibt bei Einhaltung der Clubregel keine geschlossene Geschenkkette.

Die IMO-Teilnehmer bekamen das Clubproblem übrigens in stark abstrahierter Form gestellt, um den Aufgabentext knapp zu halten und um Missverständnissen beim Übersetzen in Dutzende Sprachen vorzubeugen. Mathematisch gesehen sind die Aufgabenstellungen jedoch identisch. Die Lösungen der IMO-Probleme werden übrigens auch ausgiebig in einem Mathematikforum diskutiert.

Diesen Artikel...
  • Aus Datenschutzgründen wird Ihre IP-Adresse nur dann gespeichert, wenn Sie angemeldeter und eingeloggter Facebook-Nutzer sind. Wenn Sie mehr zum Thema Datenschutz wissen wollen, klicken Sie auf das i.
  • Auf anderen Social Networks teilen

News verfolgen

HilfeLassen Sie sich mit kostenlosen Diensten auf dem Laufenden halten:

alles aus der Rubrik Wissenschaft
Twitter | RSS
alles aus der Rubrik Mensch
RSS
alles zum Thema Numerator
RSS

© SPIEGEL ONLINE 2009
Alle Rechte vorbehalten
Vervielfältigung nur mit Genehmigung der SPIEGELnet GmbH



  • Drucken Senden
  • Nutzungsrechte Feedback
PDF-Download
PDF aufrufen... Aufgaben der IMO 2009 - PDF-Größe 243 KByte