Mathematik Olympiaden

Das Ducci-Problem Das hier gewählte Problem geht auf den italienischen Professor E. Ducci zurück, der es in den Dreißigerjahren entdeckte. Nach ihm wird oft von dem Ducci--Problem, aber auch von dem n--number--game gesprochen. Das Problem taucht in der Literatur immer wieder sporadisch auf, wurde schon bei einer Mathematik Olympiade in der UdSSR gestellt und in verschiedenen Ländern (Deutschland, Israel) im Schulunterricht verwendet. In den letzen Jahren wurden das Problem und sein Umfeld genauer unter die Lupe genommen, die meisten Beiträge finden sich in der Zeitschrift The Fibonacci Quarterly (die wichtigsten Autoren sind wohl em J.W. Creely, A. Ehrlich, A.L. Ludington, W. Webb, F.B. Wong, G. Schöffl).

Man wählt vier beliebige natürliche Zahlen und schreibt sie nebeneinander. Dann bildet man den Abstand (Betrag der Differenz) jeder Zahl zur nächsten (bei der vierten Zahl nimmt man die erste als Nachbar).

Man erhält wieder vier natürliche Zahlen. Wenn man dieses Vorgehen oft genug ausführt, enstehen lauter Nullen. Gilt dies für alle natürlichen Zahlen?

Ein Beispiel:

93	5	21	50
88	16	29	43
72	13	14	45
59	1	31	27
58	30	4	32
28	26	28	26
2	2	2	2
0	0	0	0

Beweis:

Wir bezeichnen jedes Bilden eines neuen 4-Tupels (oder Gruppe) von Zahlen als Schritt. Um die Schreibweise zu vereinfachen, verwenden wir für die Abbildung eines 4-Tupels auf das nächste das Symbol f. Offensichtlich können wir uns bei unserem Beweis auf ganze (positive!) Zahlen beschränken, da durch die Betragsbildung ab dem zweiten Schritt nur mehr ganze Zahlen vorhanden sind.

Für die Abbildung f (und beliebige ganze Zahlen a, b, c, d) gilt:

f(2a, 2b, 2c, 2d) = 2 f(a, b, c, d).

Wir können also Vielfache von ganzen Zahlen ausklammern. Weiter läßt sich zeigen, daß nach spätestens vier Schritten alle Zahlen des 4-Tupels durch 2 teilbar sind. Dies kann man leicht sehen, indem man alle 16 möglichen 4-Tupel mit Einträgen g (gerade) und u (ungerade) und die Abbildung f anwendet. Nach spätestens vier Schritten erhalten wir (g g g g).

Beginnen wir nun mit einem beliebigen 4-Tupel natürlicher Zahlen und wenden f an, dann sind nach höchstens vier Schritten alle Einträge durch 2 teilbar und wir können die 2 ausklammern. Nach weiteren vier Schritten sind die Zahlen wiederum durch 2 teilbar. Da wir unsere Abbildung f beliebig oft anwenden können, müssen nach hinreichend vielen Schritten alle Zahlen des 4-Tupels durch jede beliebig vorgegebene Potenz von 2 teilbar sein.

Da wir bei jedem Schritt die Differenz von positiven Zahlen bilden, können die Zahlen in unseren 4-Tupeln nicht anwachsen, wohl aber abnehmen. Die größte Zahl, die in einem 4-Tupel nach einer Anzahl von Schritten vorkommen kann, ist also gleich der größten Zahl im ursprünglichen 4-Tupel oder kleiner. Nach der obigen Überlegung müssen aber nach hinreichend vielen Schritten alle in dem 4-Tupel vorhandenen Zahlen durch eine beliebige Potenz von 2 teilbar sein, also auch eine Potenz von 2, die größer ist, als die größte der anfangs gewählten Zahlen.
Damit müssen alle Zahlen im 4-Tupel zu Nullen geworden sein und der Beweis ist komplett.

Weitere interessante Fragen

Natürlich drängt sich die Frage auf, ob das Verfahren auch mit 3-Tupeln, 5-Tupeln etc. klappt. Die Antwort ist Nein. Es läßt sich zeigen, daß für alle n-Tupel aus natürlichen Zahlen n zu Tupeln aus Nullen werden, wenn n eine Potenz von 2 ist. Sonst können Zyklen entstehen (daß sich die n-Tupel nach einer gewissen Anzahl von Schritten wiederholen müssen, läßt sich schon aus unserem obigen Beweis ersehen: Da die Zahlen in den Tupeln nicht wachsen können, haben wir nur eine begrenzte Anzahl von möglichen Tupeln, die sich aus einem Anfangstupel ergeben können. Wir können aber unser Verfahren unendlich oft ausführen, also muß mindestens ein Tupel mehrfach vorkommen.).

Nun stellen sich sofort zwei weiterführende Fragen: Kann man abschätzen, wieviele Schritte benötigt werden, um von einem vorgegebenen n-Tupel bis zum ersten n-Tupel in einem Zykel (bzw. einem n-Tupel aus lauter Nullen) zu gelangen? Und: Wie lange sind die Zyklen?

Die erste Frage ist für einige n = 3, 4 oder 7 beantwortet. Interessanterweise spielen die Fibonacci-Zahlen (bzw. eine Verallgemeinerung von ihnen) eine große Rolle. So benötigt man für 3-Tupel aus aufeinanderfolgenden Fibonacci-Zahlen besonders viele Schritte, um den Zyklus zu erreichen.

Die Längen von Zyklen sind genauer erforscht. Genaue Aussagen können getroffen werden, wenn sich {\em n} in der Form n=2^k, n=2^k - 2^l oder n=2^k + 2^l darstellen läßt. Alle Beweise bedienen sich der Tatsache, daß in einem Zyklus nur noch zwei verschiedene Zahlen (nämlich 0 und eine weitere ganze Zahl) vorkommen und damit das Problem auch äquivalent in einem endlichen Körper mit zwei Elementen betrachtet werden kann - also modulo 2 gerechnet werden kann. Interessanterweise treten Verwandtschaften der Zyklen zum Pascalschen Dreick (modulo 2) auf. Damit lassen sich viele Beweise elegant unter der Ausnutzung der selbstähnlichen Strukturen dieses Dreiecks führen.

Aus der Reduktion des Problems modulo 2 ergibt sich zudem eine neue Fragestellung: was passiert mit den Zyklen, wenn wir nicht mit ganzen Zahlen arbeiten, sondern mit endlichen Ringen - also nicht mehr den Abstand benachbarter Zahlen betrachten, sondern deren Addition modulo einer ganzen Zahl. Auch in diesem Fall treten Zyklen auf, deren Längen in den letzten Jahren genauer erforscht wurden.

Letzte Änderung: 16.02.2006