Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 4540. feladat (2013. április)

B. 4540. Egy börtönben n rab tartózkodik. Az unatkozó börtönőrök azt találják ki, hogy az udvaron mindegyik rab fejére piros vagy kék sapkát tesznek úgy, hogy senki se lássa, a saját fejére milyen színű kerül. Miután a rabok jól megnézték egymást (minden rab a sajátján kívül az összes többi rab sapkáját látja), mindegyiküknek le kell írnia egy-egy lapra, hogy milyen színű sapka van a fején. Aki helyesen tippel, azt másnap is kiengedik az udvarra. Melyik az a legnagyobb k szám, amelyre létezik a raboknak olyan stratégiája, amelyet követve legalább k rab biztosan kimehet másnap az udvarra?

(6 pont)

A beküldési határidő 2013. május 10-én LEJÁRT.


Megoldási ötlet: Először oldjuk meg n=2-re a feladatot.

Megoldásvázlat:

(a) Két rab esetén elérhetik, hogy pontosan egyikük jól járjon: egyikük arra tippel, hogy azonos, a másik rab pedig arra tippel, hogy különböző sapka van rajtuk.

n rab esetén a rabok k=[n/2] diszjunkt párt szervezhetnek, és a fenti módszerrel elérhetik, hogy mindegyik párból az egyik rab kimehessen másnap is.

(b) Ha a börtönőrök véletlenszerűen osztják ki a sapkákat, mindenkinek 1/2 valószínűséggel adnak kéket, illetve pirosat, függetlenül a többi sapka színétől, akkor a rabok stratégiájától függetlenül mindegyik 1/2 eséllyel nyer. Ezért a másnap is levegőző rabok számának várható értéke pontosan n/2. Ebből következik, hogy a rabok nem érhetik el, hogy [n/2]-nél több biztosan jól járjon.

A legnagyobb k tehát, amihez létezik a raboknak megfelelő stratégiája, k=[n/2].


Statisztika:

42 dolgozat érkezett.
6 pontot kapott:Ágoston Péter, Árkos Gergely, Baran Zsuzsanna, Csernák Tamás, Fehér Zsombor, Forrás Bence, Janzer Barnabás, Janzer Olivér, Jávorszky Natasa, Juhász Kristóf, Khayouti Sára, Kúsz Ágnes, Leitereg Miklós, Maga Balázs, Mócsy Miklós, Nagy Róbert, Szabó 789 Barnabás, Talyigás Gergely, Tossenberger Tamás, Weisz Ambrus, Williams Kada.
5 pontot kapott:Mezősi Máté.
4 pontot kapott:4 versenyző.
3 pontot kapott:6 versenyző.
0 pontot kapott:10 versenyző.

A KöMaL 2013. áprilisi matematika feladatai