2024 - Adventskalender der Fakultät für Informatik
„Immer dieser Fachkräftemangel“, jammert Santa vor sich hin. Die Elfen und Wichtel haben ihn zwar schon vor Jahren um eine Gehaltserhöhung gebeten, aber Santa hat diese immer abgelehnt. Jetzt sind schon seit Monaten keine neuen Bewerbungen für die anstrengenden Positionen als Wichtel eingegangen. Aber Santa ist ein Geizhals und will einfach nicht mehr bezahlen. Deswegen sind jetzt kreative, technologieoffene Lösungen gefragt.
Er hat ausgerechnet, dass ihm noch 50000 Wichtel fehlen. In einem Anfall von Panik hat er eine Wichtel-Klon-Maschine gebaut. Zum Starten braucht die Maschine ein Wichtel, diesen klont sie nach einer Stunde. Eine Stunde später wirft sie wieder 2 identische Wichtel aus. Danach wirft sie in Stunde X so viele Wichtel aus, wie sie in den letzten beiden Stunden davor ausgeworfen hat.
Wie lange muss die Maschine laufen, damit Santa gut schlafen kann?
Die Maschine produziert Wichtel nach der Fibonacci-Folge: \[ \begin{align} f_1, f_2 &= 1 \\ f_n &= f_{n-1}+f_{n-2} \text{ wenn } n>2 \end{align} \] Die Summe der n ersten Fibonacci-Zahlen ergibt sich wie folgt: \[ \sum_{i=0}^{n} f_i = f_{n+2}-1 \] Die n-te Fibonacci-Zahl kann man mithilfe des goldenen Schnitts wie folgt berechnen: \[ f_n = \left\lfloor \dfrac{1}{\sqrt{5}}\left(\dfrac{(1+\sqrt{5})}{2}\right)^n \right\rfloor \] Dies kann man nach n auflösen: \[ n \geq \log{(f_n*\sqrt{5})} / \log \dfrac{(1+\sqrt{5})}{2} \] Wenn \( f_{n+2} \) größer als 50000 sein soll, muss \[ n \geq 22,16 \] sein.
Nach 23 Stunden hat diese Maschine ausreichend viele Wichtel erstellt (das kann man auch in Wikipedia in der Tabelle nachsehen, dafür muss man keine Logarithmen rechen können).