A B. 4722. feladat (2015. május)

B. 4722. Egy $\displaystyle n$-elemű halmaz minden permutációját kiszíneztük a piros, fehér és zöld színek valamelyikével. Jelölje $\displaystyle N_{PFZ}$ azt, hogy hányféleképpen lehet egymás után egy piros, majd egy fehér, végül egy zöld permutációt végrehajtani úgy, hogy végül minden elem a helyére kerüljön vissza. Hasonlóan, jelölje $\displaystyle N_{ZFP}$ azt, hogy hányféleképpen lehet egymás után egy zöld, egy fehér, végül egy piros permutációt végrehajtani úgy, hogy végül minden elem a helyére kerüljön vissza. Mutassuk meg, hogy $\displaystyle N_{PFZ}=N_{ZFP}$.

(6 pont)

A beküldési határidő 2015. június 10-én LEJÁRT.

Megoldásvázlat. Jelöljük az $\displaystyle n$-elemű halmaz permutációinak halmazát $\displaystyle S$-el; ekkor tehát $\displaystyle P\cup F\cup Z=S$. Permutációk egymás utáni végrehajtását a két permutáció szorzatának nevezzük, tehát $\displaystyle ab$ azt a permutációt jelenti, amit úgy kapunk, hogy végrehajtjuk előbb az $\displaystyle a$, utána pedig a $\displaystyle b$ permutációt. Az identikus permutációt, amely minden elemet a helyén hagy, $\displaystyle id$-del jelöljük.

A feladatbeli jelölést terjesszük ki az $\displaystyle S$ összes részhalmazaira: tetszőleges $\displaystyle U,V,W\subset S$ esetén legyen $\displaystyle N_{UVW}$ az olyan $\displaystyle a\in U$, $\displaystyle b\in V$, $\displaystyle c\in W$ hármasok halmaza, amelyekre $\displaystyle abc=id$.

Lemma. Tetszőleges $\displaystyle U,V,W\subset S$ halmazokra

$\displaystyle N_{UVW}=N_{VWU}=N_{WUV},$

$\displaystyle N_{UVP}+N_{UVF}+N_{UVZ} = |U|\cdot |V|$

és

$\displaystyle N_{PUV}+N_{FUV}+N_{ZUV} = |U|\cdot |V|.$

Bizonyítás. Könnyen meggondolható, hogy $\displaystyle uvw=id \Leftrightarrow vwu=id \Leftrightarrow wuv=id$. Így az olyan $\displaystyle (u,v,w)\in U\times V\times W$ permutációhármasokat, amelyekre $\displaystyle uvw=id$, egyszerű ciklikus cserével megfelelhetjük azoknak a $\displaystyle (v,w,u)\in V\times W\times U$ és a $\displaystyle (w,u,v)\in W\times U\times V$ hármasoknak, amelyekre $\displaystyle vwu=id$, illetve $\displaystyle wuv=id$; ez bizonyítja az első állítást.

A második állítás bizonyításához vegyük észre, hogy minden $\displaystyle (u,v)\in U\times V$ párhoz létezik pontosan egy olyan $\displaystyle w\in S$, amelyre $\displaystyle uvw=id$. Ennek a $\displaystyle w$-nek a színe piros, fehér vagy zöld; az így kapott $\displaystyle (u,v,w)$ hármasok száma összesen $\displaystyle |U|\cdot |V|$, a $\displaystyle w$ színe szerint szétválogatva pedig $\displaystyle N_{UVP}+N_{UVF}+N_{UVZ}$.

A harmadik állítás ugyanígy bizonyítható, vagy visszavezethető az első kettőre.

Ezek után, a Lemmát többször alkalmazva,

$\displaystyle N_{PFZ} = (N_{PFP}+N_{PFF}+N_{PFZ}) -N_{PFP} -N_{PFF} =$

$\displaystyle = |P|\cdot |F| -N_{PFP} -N_{FFP} =$

$\displaystyle = (N_{PFP}+N_{FFP}+N_{ZFP}) -N_{PFP} -N_{FFP} = N_{ZFP}.$

Statisztika:

7 dolgozat érkezett.
6 pontot kapott:	Fekete Panna, Gáspár Attila, Glasznova Maja, Szebellédi Márton, Williams Kada.
3 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2015. májusi matematika feladatai