Fórum: Érdekes matekfeladatok

Tegyük fel, hogy n utas van, és ezek közül az i₁,i₂,...,i_k (ahol 1<=i₁<i₂<...<i_k<=n) sorszámú utasok őrültek. Jelöljük p_n(i₁,i₂,...,i_k)-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 p_n(1,i₂,...,i_k) alakú valószínűségeket kell kiszámolni, mivel i₁>1 esetén a keresett valószínűség p_n-i1+1(1,i₂-i₁+1,...,i_k-i₁+1) (hiszen az első i₁-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 p_k+1(1,i₂,...,i_k) valószínűségeket (ha i₁<>1, akkor p_k+1(2,3,...,k+1)=p_k(1,2,...,k)=p_k(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 p_n,m:=p_n(i₁,...,i_m) bármely i₁,...,i_m 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).

Kiegészítés: előzőleg külön kezeltük azt az esetet, amikor az utolsó utas őrült, mondván, hogy a keresett valószínűség ekkor ugyanaz, mint amikor k-1 őrült van. Ugyanis nem befolyásolja az eseményeket, hogy az utolsó utas őrült vagy sem, mivel csak az egyetlen megmaradt helyre tud ülni. Összefoglalva tehát: n utas és ezek közül bármely k őrült utas esetén (n>=k) annak valószínűsége hogy az utolsó utas a helyére ül 1/(k+1), ha az utolsó utas nem őrült, és 1/k, ha az utolsó utas őrült.

Sziasztok!

Itt az újabb példa, szintén a valség köréből (A feladat Mikulás-probléma néven is ismert).

Egy 'n' fős osztályban Mikulás ünnepségre készülnek a gyerekek. A tanár mindenkinek felírja a nevét egy cetlire, majd beteszi egy kalapba és ezután kezdődik a húzás. Miután mindenki kihúzott egyet, mi a valószínűsége annak, hogy senki sem húzta a saját nevét, azaz nem kell kezdeni mindent előről?

Sziasztok,

Szerintem az őrült utasos feladatot még ne zárjuk le. Keressünk közvetlen, számolás nélküli megoldást.

1-1/e.

Egy rokon feladat.

143. / B. 3391. Amikor Bendegúz érvényes helyjegyével felszállt a 78 személyes vasúti kocsiba, döbbenten vette észre, hogy ott már minden hely foglalt. Az történt ugyanis, hogy Dömötör helyjegy nélkül szállt fel. A többi 77 utas pedig - köztük Elek - vásárolt ugyan helyjegyet, de nem feltétlenül ültek oda, ahová a helyjegyük szólt. Bendegúz felállítja azt, aki a helyét elfoglalta. Aki feláll, az most már szintén a saját helyére szeretne leülni, és így tovább. Mindez addig folytatódik, míg végül Dömötör lelepleződik. Mennyi a valószínűsége annak, hogy Elek ülve nézheti végig az eseményeket?

(KöMaL, 2000. december)

Egy urnában k fehér és 1 fekete golyó van. Sorban kihúzzuk az összes golyót. Legyen p annak a valószínűsége, hogy utoljára fekete golyót húzunk. Ha az eseményt visszafelé történtnek képzeljük, akkor p annak a valószínűsége is, hogy ezeket a golyókat sorban az urnába dobálva elsőre fekete golyót dobunk be, azaz p=1/(k+1).

(Az őrült utasok ülései a fehér golyók, az utolsó utas ülése a fekete golyó.)

Kedve Káli gúla!

Sajnos nem értem a modelledet. Kifejtenéd kicsit bővebben? Hogyan látod pl. azonnal, hogy a keresett valség nem függ az utasok számától?

Kedves attila

A k+1 kitüntetett hely mellett a többi "normális" helyet úgy képzelem, mintha dobókockával érvénytelent dobnánk: a kocka az "élére" esne, vagy legurulna az asztalról.

k=1 őrültre a legegyszerűbb (ezt Géza figyelmeztetése előtt is láttam):

(1) Ha az örült a saját helyére ül, akkor a játék eldőlt, az utolsó utas nyer. (2) Ha az örült az utolsó utas helyére ül, akkor a játék eldőlt, az utolsó utas vesztett. (3) Minden más esetben nem történt semmi, "új őrült jön" (ld. elgurult dobókocka, vagy élére esett pénz).

Ezek szerint csak az számít húzásnak, ha az őrült a saját helyére ül, vagy az utolsóra. De honnan tudjuk, hogy ezek a húzások egyenlően valószínűek. A Te modelledben igen, de az eredeti feladatban miért is?