2024 - Adventskalender der Fakultät für Informatik
Heute ist Sinterklaas zu Besuch am Nordpol. Er und Santa wollen es sich mal so richtig gemütlich machen, oder wie Sinterklaas sagen würde „Wij maken het nu eens echt lekker gezellig“.
Andere Länder, andere Sitten: Bei Sinterklaas hat der Adventskranz 24 Kerzen und nicht nur vier, eine für jeden Tag. Er reiht die Kerzen in einem Kreis auf und stellt Santa nun folgende Aufgabe: „24 kerstelfen hebben 24 genummerde kaarsen in een cirkel opgesteld. Tot aan kerstavond willen ze elke dag een kaars aansteken. Ze besluiten daarbij steeds elke tweede kaars aan te steken die nog niet brandt. Ze beginnen op 1 december met de 2e kaars. Welke kaars wordt als laatste aangestoken?“
Santa versteht leider nur „station“ und ruft einen Elfen herbei, der Niederländisch spricht. Dieser übersetzt: „24 Weihnachtselfen haben 24 durchnummerierte Kerzen im Kreis aufgestellt, bis Heiligabend wollen sie jeden Tag eine Kerze anzünden. Sie beschließen, dabei immer jede zweite Kerze anzuzünden, die noch nicht brennt, sie starten also am 1. Dezember mit der 2. Kerze. Welche Kerze wird zuletzt angezündet?“
Jetzt versteht Santa nur noch Bahnhof. Er will sich aber keine Blöße geben. Was soll er Sinterklaas bloß antworten. Blöde Mathematik.
Welche Antwort soll Santa geben, d.h. welche Kerze wird zuletzt angezündet?
Lösung: Die Kerze Nr. 17 wird zuletzt angezündet. Das kann man auch auf Papier herausfinden, indem man die Kerzen in jeder Runde um den Kreis "eliminiert":
Mit dem Computer finden wir das auch heraus, z.B. mit der folgenden Lösung in Python:
def letzte_kerze(n):
kerzen = list(range(1, n + 1)) # Kerzen sind nummeriert von 1 bis n
index = 0 # Startpunkt
while len(kerzen) > 1:
# Lösche jede zweite Kerze
index = (index + 1) % len(kerzen) # Bestimme die Position der zu löschenden Kerze
kerzen.pop(index) # Entferne die Kerze
# Kein weiteres überspringen nötig, da nach dem Entfernen die Liste "nachrückt"
return kerzen[0] # Die letzte verbleibende Kerze
# Eingabe
n = 24
print("Letzte brennende Kerze:", letzte_kerze(n))