Egy hajón 100 rabot szállítanak egy börtönszigetre, ahonnan lehetetlen megszökni. Életfogytiglan szabadságvesztésre ítélték őket, de van egy lehetőségük a szabadulásra. [folytatás a leírásban] (? )
[...] A rabokat a börtönben ki szokták vinni sétálni egy kis udvarba. Véletlenszerűen választják ki, hogy kit visznek sétálni, és mindig egyszerre csak egyet. Ha valamikor egy rab biztosan meg tudja mondani, hogy már mindenki volt kint sétálni, akkor mindannyian megszabadulnak. Az udvarban van egy lámpa, amelynek kapcsolóját csak a rabok kezelhetik, amikor éppen sétálnak. A szigetre tartó hajón a rabok beszélgethetnek, kialakíthatnak valamilyen stratégiát, a szigeten azonban semmilyen módon nem érintkezhetnek, és nem látják a cellájukból a lámpát.
Megszabadulhatnak-e?
Tegyük fel, hogy a lámpa alapból ki van kapcsolva.
Ha 1 vagy két rab van akkor meg tudják oldani lámpa nélkül is.
Ha 3 rab van akkor meg tudják oldani a lámpával. Ha nem elsőnek visznek ki és a lámpa nincs felkapcsolva, felkapcsolod, ha fel van kapcsolva, akkor meg szólsz, hogy már mindenki volt.)
Ha ennél többen vannak, akkor ugye két biten próbálunk egy legalább 3 bit hosszú binárist tárolni, ami ugye nem fog menni.
Kellő idő múlva igen.
Választanak egy Megfigyelőt.
Ezután a következőt tehetik:
A Megfigyelő:
- ha a lámpa fel van kapcsolva, akkor lekapcsolja;
- ha a lámpa le van kapcsolva, akkor úgy hagyja
a többiek:
- ha először látja a lámpát lekapcsolva, akkor felkapcsolja
- ha nem először látja a lámpát lekapcsolva, akkor úgy hagyja
- ha a lámpa fel van kapcsolva, akkor úgy hagyja
Ezután a Megfigyelő megszámolja, hányszor kellett lekapcsolnia a lámpát. Amikor eléri a 99-et, akkor tudja, hogy mindenki más volt az udvaron, hiszen minden felkapcsolást más és más hajtott végre.
Az problémásnak tűnik, hogy amikor először megy ki a Megfigyelő, és ég a lámpa, nem tudhatja, hogy eleve fel volt kapcsolva, vagy valaki felkapcsolta már.
Ezt azzal a kiegészítéssel lehet megoldani, hogy aki az első nap megy ki, az mindenképp lekapcsolt állapotba hozza (vagy hagyja) a lámpát, és ezt nem tekinti az ő kapcsolásának. Innentől ha nem a Megfigyelő jön ki a 2-ik napon, akkor felkapcsolja, ha a Megfigyelő jön ki a 2-ik napon, akkor nem számol még semmit. Stb.
A dolog hátulütője, hogy a véletlenszerű választásból az is előállhat, hogy mindig ugyanazt viszik ki, de ez persze kis esélyű. Előbb-utóbb (a nagy számok törvénye alapján) mindenkire sor kerül, de képlékeny, hog ymikor.
Meg kell várni, amíg elég sokszor kiviszik.
Persze az nem jósolható meg, hogy mikor lesz vége.
Bár a szükséges idő várható értéke és szórása kiszámítható (nem fogom itt megtenni). Erre pedig alkalmazható a Csebisev-becslés.
Szumma szummárum, megszabadulHATnak, van rá lehetőség és esély. És ez volt a kérdés.
Bár nagy százalékod van, most sajnos nem volt jó a válaszod.
Még annyit, hogy a "biztos" és az "1 valószínűségű esemény" közti eltérésen polemizálunk.
Az én magyarázatomban 1 valószínűséggel kiszabadulnak ugye.
Ami persze nem a biztos esemény, asszem ezt kifogásolod.
Ez az egy valószínűség az erősen függ a rabok számától. Az eredeti kérdés ezt nem részletezi, és az eloszlást sem adja meg ahogy veletlenszerűen a rabokat választják.
Ha van csak száz rab, az eberi élet végső határát feszegetjük ha csak 50%-os eséllyel akarjuk a kiszabadulást, még akkor is ha minden raot ugyanolyan eséllyel visznek ki. Ha meg nem egyforma a rabok esélye, akkor meg még rosszabb.
Ha a kérdés valószínűségszámítási, akkor ki kéne számolni az esélyeket. Ha meg algoritmikus akkor meg 4+ számú rab esetén a válasz az, hogy nincs biztos stratégiájuk.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!