Problem C. 1752. (January 2023)
C. 1752. There are six people waiting in a line. It is taking very long, so they decide to play. They select a permutation of the six positions at random, and perform it three times successively. (A permutation is a rule of obtaining a new order by assigning a (possibly) new position to everyone. For example they may chose the following rule: the person at position 1 goes to position 3, the one at position 2 goes to position 1, the third goes to position 2, the fourth goes to position 6, the fifth stays in place, and the sixth goes to position 4.) What is the probability that at least one of them will be standing in their initial position at the end?
Proposed by K.\(\displaystyle \,\)A. Kozma, Győr
(5 pont)
Deadline expired on February 10, 2023.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Ismert, hogy minden permutáció felbontható közös elemmel nem rendelkező (azaz diszjunkt) körökre (ún. ciklusokra). Cikluson az elemek egy olyan sorrendjét értjük, amelyben az első elem a második helyére kerül, a második a harmadik helyére, és így tovább, a ciklus minden tagja az utána következő helyére kerül, az utolsó pedig a ciklus első tagjának a helyére. A feladatban megadott példa a következő ciklusokra bontható: \(\displaystyle (132)(46)(5)\), vagy írhatjuk a helyben maradó (azaz egy tagból álló ciklus) elhagyásával \(\displaystyle (132)(46)\) formában is. Egy ciklus hosszán a ciklust alkotó elemek számát értjük.
Most rátérünk a feladat megoldására. Mivel \(\displaystyle 6\) különböző elemnek \(\displaystyle 6!=720\) különböző permutációja van, így összesen \(\displaystyle 720\) eset van. A kedvező esetek számát a komplementer módszerrel határozzuk meg, azaz kiszámítjuk, hogy hány esetben nem kerül senki az eredeti helyére, és ezt vonjuk majd ki a \(\displaystyle 720\)-ból.
Ha senki nem kerül az eredeti helyére, akkor a permutáció nem tartalmazhat \(\displaystyle 1\) hosszú kört, mert az abban szereplő elem helyben maradna. Hasonlóképpen nem tartalmazhat \(\displaystyle 5\) hosszú kört sem, mert akkor \(\displaystyle 1\) elem maradna ki, és az szükségképpen az eredeti helyén maradna. Mivel a permutációt \(\displaystyle 3\)-szor egymás után hajtjuk végre, ezért \(\displaystyle 3\) hosszúságú kört sem tartalmazhat, mert az azt jelentené, hogy annak elemei a harmadik lépésben visszakerülnének az eredeti helyükre. Megállapításainkból az következik, hogy a permutáció kizárólag \(\displaystyle 2\), vagy \(\displaystyle 4\) vagy \(\displaystyle 6\) hosszú ciklusokat tartalmazhat, ezekben az esetekben a háromszori ismétlődéssel sem kerül senki a helyére. Tudjuk, hogy \(\displaystyle 6=2+4=2+2+2\), ezért vagy egy \(\displaystyle 6\) hosszú ciklusból áll a permutáció, vagy van egy \(\displaystyle 2\) és egy \(\displaystyle 4\) hosszú kör, vagy a permutáció \(\displaystyle 3\) darab \(\displaystyle 2\)-es körből áll. Ha a permutáció egyetlen ciklusból áll, azaz a \(\displaystyle 6\) elemet egy kör mentén állítjuk sorba, az \(\displaystyle 5!=120\) különböző esetet jelent. Ha van egy \(\displaystyle 2\)-es kör, akkor annak \(\displaystyle 2\) elemét a \(\displaystyle 6\) elemből \(\displaystyle \binom{6}{2}=15\)-féleképpen válaszhatjuk ki, a maradék \(\displaystyle 4\) elemet pedig \(\displaystyle 3!=6\)-féleképpen permutálhatjuk egy kör mentén, így \(\displaystyle 15 \cdot 6=90\) ilyen eset van. Ha \(\displaystyle 3\) darab \(\displaystyle 2\)-es ciklus van, akkor azok sorrendje nem számít, így ezek száma \(\displaystyle \displaystyle{\frac{\binom{6}{2} \cdot \binom{4}{2} \cdot \binom{2}{2}}{3!}=\frac{15 \cdot 6}{6}=15}\).
Összesen \(\displaystyle 120+90+15=225\) esetben nem kerül vissza senki az eredeti helyére, tehát \(\displaystyle 720-225=495\) esetben legalább egy ember az eredeti helyére kerül.
A kérdezett valószínűség értéke \(\displaystyle \displaystyle{p=\frac{495}{720}=\frac{11}{16}}(=0,6875)\).
Statistics:
24 students sent a solution. 5 points: Hosszu Noel, Keszthelyi Eszter, Mészáros Anna Veronika, Schneider Dávid, Sipeki Márton, Tomesz László Gergő, Varga Dániel 829, Waldhauser Miklós. 4 points: Seprődi Barnabás Bendegúz, Szabó Viktória Ildikó . 3 points: 3 students. 2 points: 3 students. 0 point: 2 students. Unfair, not evaluated: 1 solutions.
Problems in Mathematics of KöMaL, January 2023