A B. 4491. feladat (2012. november)

B. 4491. 100 elítélt nevét valamilyen sorrendben beleteszik 100 sorszámmal ellátott fiókba. Ezek után az egyszemélyes celláikból egyesével véletlenszerűen behívják a rabokat. Mindegyikük tetszése szerint kihúzhat egyesével 50 fiókot. Ha megtalálta valamelyikben a saját nevét, akkor elvezetik egy külön terembe, ha nem, akkor az összes elítéltet azonnal kivégzik. Végül, ha mindannyian szerencsével jártak, valamennyiüket szabadon engedik. Mutassuk meg, hogy e szabályok ismeretében a rabok ki tudnak dolgozni egy olyan stratégiát, amelyet alkalmazva 30%-nál nagyobb az esélye annak, hogy kiszabadulnak.

(6 pont)

A beküldési határidő 2012. december 10-én LEJÁRT.

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

Statisztika:

46 dolgozat érkezett.

6 pontot kapott: 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 pontot kapott: Simon 047 Péter.

0 pontot kapott: 10 versenyző.

Nem versenyszerű: 1 dolgozat.

A KöMaL 2012. novemberi matematika feladatai

46 dolgozat érkezett.
6 pontot kapott:	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 pontot kapott:	Simon 047 Péter.
0 pontot kapott:	10 versenyző.
Nem versenyszerű:	1 dolgozat.

Már regisztráltál?
Új vendég vagy?