Also noch der Beweis:
Deine gesuchte Zahl ist 162. Für die ersten drei Stufen brauchst du 6 Steine (dafür brauchst du keine Simulation, dafür Wertest du die Summe über k*(0.5)^k von 1 bis unendlich aus (Der Erwartungswert für die Anzahl der Schritte um ein Feld nach oben zu kommen, wenn du nicht nach unten darfst. (habe ich, ehrlich gesagt, Maple machen lassen). Du hast Drei solcher Stufen, brauchst im Mittel also sechs Steine, um auf Stufe 3 zu kommen.
Jetzt beginnt der interessante Teil der Rechnung. Im
Matheboard habe ich den entscheidenen Hinweis auf die Rekursionsvorschrift bekommen, ihn in eine Matrix umgeschrieben und Matlab drauf losgelassen, was mir dann die untere Matrix in meinem Post dort gebracht hat. (in der oberen habe ich statt 0.5 eine 3 geschrieben, weil die Matrix sonst nicht ins Fenster gepasst hätte. Ausserdem ist n=15 gewählt, bei deinem Spezialfall ist natürlich n=12 notwendig, da die ersten drei Schritte oben schon abgehandelt wurden. Diese Matrix führt dann auf eine durchschnittliche Steinanzahl bis zum ersten erreichen der letzten Stufe von 156. (Wenn man die Matrix zu Fuss löst, kommt man auf n(n+1)=12*13=156)
Mit den Sechs Steinen von oben dann also auf die 162 die du in der Simulation auch gefunden hast.
Wenn also SFix deine Stufenanzahl ist, bei denen du nicht fallen kannst und SFall deine Stufenanzahl mit Fallmöglichkeit, brauchst du also durchschnittlich
Steine, um die höchste Stufe das erste Mal zu erreichen. Und das sollte fast in geringerer Zeit als ein random(2)-Aufruf zu berechnen sein
Code:
(Matlab)
% Matrixdarstellung und Gauß
%
% n=12;
%
% M=zeros(n,n+1);
%
% for j=1:(n)
% M(j,n+1)=1;
% end
%
% for j=(1:n-2)
% M(j+1,j+1)=1;
% M(j+1,j)=-0.5;
% M(j+1,j+2)=-0.5;
% end
% end
%
% M(1,1)=0.5;
% M(1,2)=-0.5;
% M(n,n)=1;
% M(n,n-1)=-0.5;
%
%
% rref(M)
% Auswertung der gefundenen Formel n(n+1)
n=30;
N=zeros(2,n);
for i=1:n
N(1,i)=i;
if i<5
N(2,i)=i*2;
else
s=i-3;
N(2,i)=6+s*(s+1);
end
end