Problem B. 4491. (November 2012)

B. 4491. The names of 100 convicts are placed in 100 numbered drawers in some order. Then the convicts are brought one by one from their cells in a random order, and each of them is allowed to pull out 50 drawers one by one. If he finds his own name in a drawer then he is led to a separate room. Otherwise all 100 convicts are executed immediately. Finally, if each of them succeeds, they are all set free. Show that, knowing the rules, the prisoners can follow a strategy that results in a larger than 30% probability of going free.

(6 pont)

Deadline expired on December 10, 2012.

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

Útmutatás: Permutációk felbontása ciklusokra.

Megoldás: Az egyszerűség kedvéért legyenek a fiókok 1-től 100-ig számozva, a rabok pedig szintén számozzák meg magukat 1-től 100-ig. Ekkor az elítéltek nevének a fiókokban történő lehetséges elhelyezései megfeleltethetők az $1,2,\ldots,100$ számok permutációinak. Feltételezzük, hogy a 100! darab permutáció közül mindegyikre ugyanakkora valószínűséggel esik a választás a nevek elhelyezése során. Ekkor egy célravezető stratégia a következő. Minden rab először a saját sorszámával megegyező sorszámú fiókot húzza ki. Ha a saját nevét találta benne, akkor elvezetik a külön terembe. Ha nem, akkor kihúzza azt a fiókot, amelyiknek a sorszámát az első fiókban találta, és így tovább. Azt állítjuk, hogy a permutációk több mint 30%-a olyan, hogy mind a 100 elítélt az első 50 húzás során megtalálja a saját sorszámát (nevét).

Ehhez tekintsük a permutációk diszjunkt ciklusokra való felbontását. Ez a következőképpen történik. Ha a $\pi$ permutáció az i-t $\pi$ (i)-be viszi, akkor $\pi$ (i)-t $\pi$ ( $\pi$ (i))= $\pi$ ²(i)-be viszi, és így tovább. Az $i, \pi(i), \pi^2(i)\ldots$ számok nem lehetnek mind különbözők, tehát van olyan $\alpha$ < $\beta$ , hogy $\pi^{\alpha}(i)=\pi^\beta(i)$ . Tegyük fel, hogy k= $\beta$ - $\alpha$ a lehető legkisebb. Ekkor $\pi$ ^k(i)=i és az $i, \pi(i),\ldots,\pi^{k-1}(i)$ számok mind különbözők. A $\pi$ permutáció tehát ciklikusan permutálja egymás között az $i, \pi(i),\ldots,\pi^{k-1}(i)$ számokat. Nyilván a fennmaradó számokat is egymás között permutálja, így az előző gondolatot használva azok között is található egy részhalmaz, melynek elemeit egymás között permutálja. Ezt az eljárást folytatva az $1,2,\ldots,100$ számokat beoszthatjuk úgy részhalmazokba hogy $\pi$ minden egyes részhalmaz elemeit egymás között ciklikusan permutálja. Elképzelhető az is, hogy valamely i-re $\pi$ (i)=i. Ekkor egy 1 hosszúságú ciklussal állunk szemben, ami azt jelenti, hogy az i-edik rab rögtön az első kihúzott fiókban a saját nevét találja.

Nyilván akkor fog az összes rab kiszabadulni, ha az adott $\pi$ permutáció diszjunkt ciklusokra történő felbontásában mindegyik ciklus legfeljebb 50 hosszúságú. A rossz permutációk tehát azok, melyekben található legalább 51 hosszú ciklus. Ilyen persze legfeljebb egy lehet benne. Számoljuk össze a rossz permutációkat. Legyen 51 $\le$ t $\le$ 100. Azon permutációk száma, melyekben van egy t hosszú ciklus,

$\binom{100}{t}\cdot \frac{t!}{t}\cdot (100-t)!=\frac{100!}{t},$

hiszen a ciklus elemei $\binom{100}{t}$ -féleképpen választhatók ki, ezeket $\frac{t!}{t}$ -féleképpen rendezhetjük ciklusba, a fennmaradó elemeknek pedig mind a (100-t)! sorrendje választható. A rossz permutációk aránya eszerint

$\frac{1}{51}+\frac{1}{52}+\ldots+\frac{1}{100}\approx 0,688<0,7.$

Azon permutációk aránya tehát, amelyek mellett a rabok kiszabadulnak, valóban nagyobb 0,3-nál.

Statistics:

46 students sent a solution.

6 points: Andó Angelika, Bajnok Anna, Bereczki Zoltán, Bogáromi Dávid, Demeter Dániel, Fehér Zsombor, Fonyó Viktória, Géczi Péter Attila, Hansel Soma, Havasi 0 Márton, Herczeg József, Janzer Barnabás, Janzer Olivér, Kaprinai Balázs, Katona Dániel, Kúsz Ágnes, Lajos Hanka, Leitereg András, Leitereg Miklós, Maga Balázs, Makk László, Mócsy Miklós, Nagy Róbert, Qian Lívia, Rovó Judit, Schwarcz Tamás, Somogyvári Kristóf, Szabó 262 Lóránt, Szaksz Bence, Talyigás Gergely, Tardos Jakab, Tossenberger Tamás, Török Zsombor Áron, Williams Kada.

5 points: Simon 047 Péter.

0 point: 10 students.

Unfair, not evaluated: 1 solutions.

Problems in Mathematics of KöMaL, November 2012

46 students sent a solution.
6 points:	Andó Angelika, Bajnok Anna, Bereczki Zoltán, Bogáromi Dávid, Demeter Dániel, Fehér Zsombor, Fonyó Viktória, Géczi Péter Attila, Hansel Soma, Havasi 0 Márton, Herczeg József, Janzer Barnabás, Janzer Olivér, Kaprinai Balázs, Katona Dániel, Kúsz Ágnes, Lajos Hanka, Leitereg András, Leitereg Miklós, Maga Balázs, Makk László, Mócsy Miklós, Nagy Róbert, Qian Lívia, Rovó Judit, Schwarcz Tamás, Somogyvári Kristóf, Szabó 262 Lóránt, Szaksz Bence, Talyigás Gergely, Tardos Jakab, Tossenberger Tamás, Török Zsombor Áron, Williams Kada.
5 points:	Simon 047 Péter.
0 point:	10 students.
Unfair, not evaluated:	1 solutions.

Already signed up?
New to KöMaL?