 Tegyük fel, hogy n utas van, és ezek közül az i1,i2,...,ik (ahol 1<=i1<i2<...<ik<=n) sorszámú utasok őrültek. Jelöljük pn(i1,i2,...,ik)-val annak valószínűségét, hogy az utolsó utas a helyére tud ülni. Tegyük fel, hogy a szóban forgó valószínűségeket már ismerjük n-nél kevesebb utas és ezek közül bármely k,k-1,k-2,...,1 őrült esetén. Világos, hogy ekkor már csak a pn(1,i2,...,ik) alakú valószínűségeket kell kiszámolni, mivel i1>1 esetén a keresett valószínűség pn-i1+1(1,i2-i1+1,...,ik-i1+1) (hiszen az első i1-1 utasig rendben mennek a dolgok), amit a feltevés szerint már ismerünk. Természetesen ahhoz, hogy egyáltalán ilyen módon k őrült esetén el tudjunk indulni, ismerni kell a pk+1(1,i2,...,ik) valószínűségeket (ha i1<>1, akkor pk+1(2,3,...,k+1)=pk(1,2,...,k)=pk(1,2,...,k-1) valószínűségről van szó, mivel mindegy hogy az utolsó utas őrült -e vagy sem, úgyis csak az egyetlen üres helyre tud ülni). A továbbiakban egyszerűsítjük a jelölést, mivel indukcióval feltesszük, hogy k-nál kevesebb őrült esetén a valószínűség független attól, hogy pontosan mely utasok őrültek, vagyis pn,m:=pn(i1,...,im) bármely i1,...,im kombináció esetén. Mint azt egy őrült esetén láttuk, a feltevés jogos. Tehát van k+1 utasunk, az első k utas őrült. Feltehetjük, hogy az utolsó utas nem őrült, mert ez nem befolyásolja a keresett valószínűséget (így is úgy is csak az egyetlen megmaradt helyre tud ülni), ha pedig őrült lenne, akkor nyilván eggyel kevesebb őrülttel kellene megoldani a feladatot, amit már a feltevés szerint megoldottunk. Ekkor
. A fenti képletben az 1. utas (aki őrült) 1/(k+1) valószínűséggel ül bármely helyre. Ha saját vagy másik őrült helyére ül, akkor a leültetendő utasok és az őrültek száma 1-gyel csökken, ezt nyilván k féleképpen teheti meg. Az egyetlen normális utas (utolsó utas) helyére nem ülhet, mert akkor biztos hogy az utolsó utas nem ül a saját helyére. Most teljes indukcióval feltesszük, hogy minden n-re, és minden m<k őrültre a keresett valószínűség 1/(m+1). Ez m=1-re már bizonyított. Ekkor a fenti képlet szerint
. Most rögzített k őrültszám mellett n szerinti teljes indukcióval haladunk (n>k), és feltesszük, hogy adott k mellett n-1,n-2,...,k+1 utassal a keresett valószínűség utasszámtól és őrültek kombinációjától függetlenül 1/(k+1).
. Az első utas (aki őrült) 1/n valószínűséggel ül bármely helyre, ebből k esetben őrült helyére (a sajátját is beleértve). Ha őrült helyére ült, akkor az utasok és az őrültek száma is 1-gyel csökken, mely esetre ismerjük a valószínűséget (1/k). Ha nem őrült helyére és nem is az utolsó helyre ül (n-k-1 eset), akkor az utasok száma 1-gyel csökken, de akinek a helyére ült, az megőrül, vagyis az őrültek száma marad. Az indukciós feltevés szerint ez esetekben is ismerjük a valószínűséget (1/(k+1)). Innen n utasra és k őrültre (ahol az 1. utas biztos őrült) a keresett valószínűség 1/(k+1) és független az őrültek kombinációjától, ha n-nél kevesebb utasra is fügetlen volt (ez az indukciós feltevés).
|
