Noch n Rätsel

[MudGuard]

Hi,

"In einem alten Kloster werden drei Stapel aus 64 verschieden großen Holzscheiben aufbewahrt. Einst befanden sich alle Scheiben so auf einem Stapel, dass jeweils die nächstkleinere auf der vorhergehenden lag. Seither legen die Mönche am Ende jeder Stunde eine der obenliegenden Scheiben um. Diese Scheibe legen sie immer auf eine größere, obenliegende Scheibe oder auf einen freien Platz. Es gibt allerdings nie mehr als drei Stapel. Die Sage geht, dass die Welt untergeht, sobald an einem anderen Ort der ursprüngliche Stapel wiederersteht."

Wenn die Mönche dabei systematisch vorgehen, ist das nach (2^64) - 1 *) Stunden =
18.446.744.073.709.551.616 Stunden =
768.614.336.404.564.650,66... Tagen =
2.104.351.365.926.255,03... Jahren =
2,1 * 10^15 Jahren = 2,1 Billiarden Jahren
der Fall.

Wann haben die angefangen? Bleibt noch Zeit, den Tee auszutrinken?

*)
Für eine Scheibe: 1 Bewegung
Für n + 1 Scheiben: der auf der größten Scheibe liegende Stapel muß auf einen freien Platz verschoben werden, dann die größte Scheibe bewegt werden, dann der Stapel wieder auf die größte Scheibe ==> Schritte für n Scheiben plus 1 Schritt für die größte Scheibe plus Schritte für n Scheiben ==> f(n+1) = 2f(n) + 1

f(1) = 1
f(2) = 2 f(1) + 1 = 3
f(3) = 2 f(2) + 1 = 7
...

Behauptung: das ist gleichbedeutend mit f(n) = 2^n - 1

für 1 gilt: 2^1 - 1 = 1
für n > 1 gilt: f(n) = 2f(n - 1) + 1 = 2(2^(n-1) - 1) + 1 = 2*2^(n-1) - 2 + 1 = 2^n - 1

qed.

(hey, ich kann ja noch den Beweis per vollständiger Induktion)

cu,
Andreas