Ein Weihnachtsbaum soll mit Christbaumkugeln und Schokoladenuhren behängt werden, die in einer Reihe vor dem Baum liegen. Dabei liegen anfangs sieben Kugeln links und sieben Uhren rechts. Die Tradition will jedoch folgendes: Wenn direkt rechts neben einer Kugel eine Uhr liegt, werden beide Objekte vertauscht und eine weitere (neue) Schokoladenuhr wird dazwischengelegt. Dies wiederholt sich solange, bis sich alle Uhren links von den Kugeln befinden. Daraufhin wird der Weihnachtsbaum mit den Kugeln und Uhren behängt.
Aufgabe:
Wieviele Objekte hängen am Ende im Baum?
Antwort:
Es sind 903. Am Ende hängen 896 Uhren und 7 Kugeln am Baum.
Der Gewinner ist Kevin Lange aus Borgentreich. Insgesamt erreichten 686 Einsendungen die Redaktion.
Lösung:
Dafür schauen wir uns kleinere Beispiele an.
Die Situation mit einer Kugel und einer Uhr sieht folgendermaßen aus: KU. Eine Uhr befindet sich rechts von einer Kugel. Nach dem Vertauschen ist die Situation: UUK. Zwei Uhren liegen links von der Kugel und der Prozess endet.
Betrachten wir jetzt 3 Kugeln und 3 Uhren. Zur besseren Übersicht sind die Kugeln nummeriert. Die Startlage ist
K<small>3</small> K<small>2</small> K<small>1</small> UUU
Wir betrachten jetzt nur die Wanderung von K<small>1</small>. Jedesmal, wenn K<small>1</small> mit einer Uhr die Plätze tauscht, wird rechts eine Uhr entfernt und 2 Uhren werden nach links gelegt. Die erste Kugel entfernt rechts also 3 Uhren und legt 6 nach links, also
K<small>3</small> K<small>2</small> UUUUUU K<small>1</small>
Die zweite Kugel K<small>2</small> entfernt diese 6 Uhren von ihrer Rechten und legt die doppelte Menge also 12 nach links
K<small>3</small> UUUUUUUUUUUU K<small>2</small> K<small>1</small>
Die letzte Kugel K<small>3</small> arbeitet sich durch diese 12 Uhren und endet mit der doppelten Anzahl, also 24 links von sich. Damit endet der Prozess. Insgesamt liegen jetzt 24 Uhren und 3 Kugeln vor dem Baum.
Die Struktur, die man erkennen kann:
Jede Kugel muss durch alle Uhren direkt rechts von ihr durchgetauscht werden und verdoppelt dabei deren Anzahl. Die Startzahl von Uhren n<small>U</small> wird also von jeder der n<small>K</small> Kugeln verdoppelt. Insgesamt liegen am Ende
2n<small>K</small> ∙ n<small>U</small>
Uhren links.
Die Zahl der Kugeln ändert sich nicht. Es bleiben n<small>K</small> Stück. Insgesamt liegen also
2n<small>K</small> ∙ n<small>U</small> +n<small>K</small>
Objekte vor dem Baum.
Bei
n<small>U</small> = n<small>K</small> = 7
sind das also
27 ∙ 7 + 7 = 903
Von den 903 Objekten sind 7 Kugeln und 896 Schokoladenuhren.