Közismert fejtörő feladvány, hogy 100 rab áll egymás mögött egy sorban, mindenkinek a fején egy sapka, vagy kék, vagy piros teljesen véletlenszerűen, és mindenki csak az előtte állók sapkáját látja. Mindenki tippelhet a saját sapkájának a színére úgy, hogy a tippjét a többiek is hallják. Amikor mindenki tippelt, elengedik azokat, akik helyesen tippeltek. Előzetesen a rabok megbeszélhetnek stratégiát, és azt is, hogy milyen sorrendben tippelnek majd, de később már semmilyen kommunikáció nem megengedett a nyilvános tippeken kívül. Hány rab menekülhet meg biztosan?

Aki nem ismerte még ezt a feladatot, gondolkodjon el rajta, mielőtt tovább olvas. Aki csak 50 rabot tudna megmenteni, és azt se biztosan, az gondolkodjon tovább. Fontos: nem az a kérdés, hogy átlagosan mennyit tudunk megmenteni, hanem olyan stratégia kellene, amivel a lehető legtöbb rab biztosan szabadul. Ha valaki csak 50-et tud biztosan megmenteni, az is gondolkodjon tovább, egyébként is ki lenne az, aki beáldozná magát a többieket segítve? Az állítás az, hogy 99 rab biztosan megmenthető, és a kimaradó rabnak sem kell beáldoznia magát, azaz 50 százalék esélye van menekülni – akkor is ha segít a többieknek, és akkor is ha nem. Az ugye nyilvánvaló, hogy aki elsőként tippel, nem mehet biztosra, mert a saját sapkáját nem látja, és még semmi információ nem hangzott el, tehát 99-nél többet biztosan megmenteni nem lehet. De hogyan lehet 99-et?

A megoldáshoz a színekhez 0 és 1 számokat rendelünk. A tippelést a leghátsó rabtól kezdjük, aki magán kívül mindenkit lát. Ő adja össze az összes előtte lévő számot, és mondjon 0-át, azaz a 0-nak megfelelő színt, ha az összeg páros, és 1-et, ha az összeg páratlan. Ezután a rabok haladjanak előrefelé a tippeléssel. A leghátsó előtti rab mindenkit lát, akit a leghátsó látott, csak magát nem, így ki tudja számítani, hogy milyen sapka van a fején. Ha például az előtte lévő összeg páros, és a hátsó páratlant mondott, akkor rajta csakis 1-es sapka lehet. Miután bemondja a tippjét, ami helyes, az előtte lévő rab ezt ki tudja vonni a leghátsó által bemondott összegből, látja továbbá ő is az előtte lévőket, így teljesen hasonló módon ki tudja számolni ő is a sapkája színét, amit bemondhat, és így tovább.

160. feladvány: Sapkás rabok összevissza

Ez a feladvány a bevezetőben ismertetett feladványnak egy általánosított variációja. Néhány dolgot változtatunk. Az egyik az, hogy az egyszerűség kedvéért legyenek csak tízen a rabok. A másik, hogy a rabokat összevissza állítják a sorba: némelyik előre, némelyik hátrafelé néz véletlenszerűen, mégpedig egyforma valószínűségekkel. Tehát mindenki a sornak az egyik felét látja, de véletlenszerű, hogy melyiket. Tegyük fel, hogy amikor már sorban állnak, de még mielőtt a sapkákat megkapják meg kell beszéljék azt, hogy milyen sorrendben tippelnek. Ekkor még mindenki mindenkit lát (forgathatják a fejüket). Miután ezt eldöntötték, megkapják a sapkákat véletlenszerűen kétféle színben.

A kérdés: Mi a valószínűsége annak, hogy olyan sorrendbe állítják a rabokat, hogy egy kivétellel mindenkit biztosan meg tudnak menekíteni maguk közül?

Bónusz kérdések haladóknak: Hányat lehet biztosan megmenti általában, egy tetszőleges, de adott konfigurációban? Mi a rabságban maradó rabok számának várható értéke? Mi a helyzet akkor, ha a tippelési sorrendet nem kell előre eldöntsék, hanem akár a látott sapkák is befolyásolhatják azt, viszont biztosítaniuk kell, hogy ne szólalhassnak meg egyszerre, és az időérzékükre nem alapozhatnak ebben. Van-e olyan konfiguráció akárhány rab esetében, amikor ez utóbbi esetben többet tudnak megmenteni maguk közül, mint egyébként?

Nehézségi szint:

A megfejtéseket részletes magyarázattal együtt az eszventura@qubit.hu címre várjuk. A leggyorsabb és legkreatívabb megoldást küldő versenyzőink felkerülnek az Ész Ventura dicsőségfalára, közöttük és minden jó megoldást beküldő versenyző között év végén nyereményeket sorsolunk ki. Fiatal megoldóinktól kérjük, hogy tüntessék fel életkorukat és évfolyamukat, mert körükben különdíjakat is ki fogunk sorsolni. Az e-mail subject mezőjében kérjük továbbá sorszámmal jelezni, hogy melyik feladvány megoldásáról van szó. Beküldési határidő: szeptember 30. éjfél.

Az Ész Ventura feladványügyi rovat gazdája: Gáspár Merse Előd fizikus, kognitív kutató, társasjáték-fejlesztő és bűvész.