© Friederike Hofmann, MATH+
Autor*in: Christian Hercher (Europa-Universität Flensburg)
Aufgabe
Wichtelin Collean spielt in ihrer Freizeit gern mit natürlichen Zahlen. (Anmerkung der Redaktion: Für Collean gehört die Null nicht zu den natürlichen Zahlen.) Dabei ist ihr aufgefallen, dass immer dann, wenn sie eine ungerade natürliche Zahl n betrachtet, deren Dreifaches wieder ungerade ist, d. h. 3n+1 ist durch zwei teilbar. Deshalb denkt sie sich folgende zwei Regeln aus, wie sie aus einer natürlichen Zahl n eine weitere errechnen kann:
- Ist die betrachtete Zahl n gerade, so teilt sie sie durch zwei und erhält als nächste Zahl \frac{n}{2} . Da das Ergebnis kleiner ist als die Ausgangszahl, nennt Collean dies einen Verkleinerungsschritt.
- Ist die betrachtete Zahl n aber ungerade, so multipliziert sie diese erst mit drei, addiert dann eins und teilt das Ergebnis durch zwei. (Dass dies immer funktioniert, haben wir oben gesehen.) Also erhält sie als nächste Zahl \frac{3n+1}{2} . Hier ist das Ergebnis größer als die Ausgangszahl. Dementsprechend spricht Collean in diesem Fall von einem Vergrößerungsschritt.
Auf diese Weise kann Collean, beginnend mit einer beliebigen natürlichen Zahl, immer weitere erhalten. Beginnt sie etwa mit der Zahl 11, so erhält sie als nächste Zahl die 17, dann die 26, die 13, 20, 10, 5, 8, 4, 2 und schließlich die 1. Dann passiert etwas Seltsames: Nach der 1 erhält sie nach ihren Regeln wieder die 2, dann wieder die 1, dann wieder 2, und so weiter und so fort.
Collean fragt sich, ob dies immer so ist: Gelangt man, egal, mit welcher Zahl man anfängt, irgendwann immer in diese Schleife von 1 zu 2? Jedenfalls deuten alle Beispiele, die sie ausprobiert, in diese Richtung. Ein Beweis ist das aber natürlich noch lange nicht …
Aber als mathematisch interessierte Wichtelin gibt sie sich mit dem Aufstellen dieser Vermutung natürlich nicht zufrieden. Zwar ist deren Beweis wohl noch außerhalb ihrer Reichweite, aber man kann ja vielleicht einige kleinere Beobachtungen in diesem Kontext machen und diese dann beweisen oder widerlegen. So stellt sie folgende Thesen über ihre beiden Regeln auf:
Behauptung A: Lässt sich eine natürliche Zahl n als a\cdot 2^k-1 (mit natürlichen Zahlen a und k ) schreiben, so folgen auf die Zahl n mindestens k Vergrößerungsschritte hintereinander.
Behauptung B: Es gibt eine natürliche Zahl n , auf die nur noch Vergrößerungsschritte folgen.
Behauptung C: Folgen auf eine ungerade natürliche Zahl n zunächst mindestens ein Vergrößerungsschritt und danach direkt hintereinander zwei Verkleinerungsschritte, so kann man die so konstruierte Zahl m auch erhalten, indem man mit der Startzahl \tfrac{n-1}{2} angefängt.
Behauptung D: Wenn es Startzahlen gibt, für welche man nie bei 1 ankommt, dann lässt die kleinste unter ihnen bei Division durch 6 den Rest 1 oder den Rest 3.
Welche der Behauptungen A bis D sind richtig?
Sonntagsbonus + Fehler: Für diese Aufgabe gibt es eine Zeitgutschrift von 48 Stunden.
Antwortmöglichkeiten:
- Alle vier Behauptungen sind richtig.
- A, B und C sind richtig, D ist falsch.
- A, B und D sind richtig, C ist falsch.
- A, C und D sind richtig, B ist falsch.
- B, C und D sind richtig, A ist falsch.
- A und B sind richtig, C und D sind falsch.
- B und C sind richtig, A und D sind falsch.
- A ist richtig, B, C und D sind falsch.
- D ist richtig, A, B und C sind falsch.
- Alle vier Behauptungen sind falsch.