A C. 1752. feladat (2023. január)

C. 1752. Hatan sorban állnak. Sokat kell várniuk, ezért játékból egy bizonyos szabály szerint sorrendet cserélnek és azt háromszor egymás után végrehajtják. Egy ilyen szabály (ún. permutáció) például: az 1. a 3. helyre áll, a 2. az 1. helyre, a 3. a 2. helyre, a 4. a 6. helyre, az 5. az 5. helyen marad, végül a 6. a 4. helyre áll. Mekkora a valószínűsége, hogy legalább az egyikük az eredeti helyére kerül?

Javasolta: Kozma Katalin Abigél (Győr)

(5 pont)

A beküldési határidő 2023. február 10-én LEJÁRT.

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ön­bö­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 komp­lementer 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 e­le­mei a harmadik lépésben visszakerülnének az eredeti helyükre. Megállapításaink­bó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)$.

Statisztika:

24 dolgozat érkezett.
5 pontot kapott:	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 pontot kapott:	Seprődi Barnabás Bendegúz, Szabó Viktória Ildikó .
3 pontot kapott:	3 versenyző.
2 pontot kapott:	3 versenyző.
0 pontot kapott:	2 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2023. januári matematika feladatai