 |
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