Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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