Problem B. 4540. (April 2013)

B. 4540. There are n prisoners in a prison. The guards were bored, so they invented the following game: In the courtyard, they place either a red cap or a blue cap on the head of each prisoner. The prisoners are then given some time to look at one another (each prisoner can see all caps but his own), and then each of them has to write down on a sheet of paper what colour he thinks his cap is. Those guessing correctly are allowed to walk in the courtyard the following day, too. What is the largest number k for which the prisoners may follow an appropriate strategy to make it certain that at least k of them are allowed to walk in the courtyard the following day?

(6 pont)

Deadline expired on May 10, 2013.

Sorry, the solution is available only in Hungarian. Google translation

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].

Statistics:

42 students sent a solution.
6 points:	Á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 points:	Mezősi Máté.
4 points:	4 students.
3 points:	6 students.
0 point:	10 students.

Problems in Mathematics of KöMaL, April 2013