Permutációs játékok – egyetemi oktatás
Waldhauser Tamás, Torma Bence
SZTE, Bolyai Intézet
Játék az Oktatásban és Kutatásban Konferencia
Neumann János Egyetem
Kecskemét, 2019.06.24.
Permutációk a matematika szakon
- permutáció fogalma: \(\;\; \pi\colon A \rightarrow A\) bijekció
- permutációk szorzása: \(\;\; a(\rho\pi) = (a\rho)\pi \)
- idegen ciklusok szorzatára való felbontás
- előállítás transzpozíciók szorzataként
- páros és páratlan permutációk
- az \( S_n \) szimmetrikus csoport és az \( A_n \) alternáló csoport
- permutáció rendje
- konjugálás, \( S_n \) normálosztói, \( A_n \) egyszerűsége
Előállítás transzpozíciók szorzataként
 |
\( \pi \) |
 |
\( \pi\cdot(12) \) |
 |
\( \pi\cdot(12)\cdot(24) \) |
 |
\( \pi\cdot(12)\cdot(24)\cdot(36) \) |
 |
\( \pi\cdot(12)\cdot(24)\cdot(36)\cdot(45) \) |
| \( \pi\cdot(12)(24)(36)(45) = \operatorname{id} \) | \( \ \implies \ \pi = (45)(36)(24)(12) \) |
Tétel
Minden permutáció előállítható transzpozíciók szorzataként.
Bizonyítás
Mindig ki tudom rakni a játékot. ∎
Másik bizonyítás
Elég ciklusokra igazolni: \( (a_1\,a_2\cdots a_k)=(a_1a_2)(a_1a_3)\cdots(a_1a_k). \) ∎
Meg lehet-e csinálni ennél kevesebb lépésből?
Legyen \(\ c(\pi)\ \) a \(\ \pi\ \) permutáció ciklusainak száma (beleértve a fixpontokat, mint 1 hosszúságú ciklusokat is).
Tétel
Minden \(\ \pi\ \) permutáció és \(\ (ab)\ \) transzpozíció esetén \[ c(\pi\cdot(ab))=c(\pi)\pm1.\]
Következmény
- A minimális lépésszám \(\ n-c(\pi) \).
- A megoldási stratégiánk optimális.
- Az \(\ (a_1\,a_2\cdots a_k)=(a_1a_2)(a_1a_3)\cdots(a_1a_k) \) felbontás is optimális.
- Isten száma \(\ n-1 \).
- Az átlagos lépésszám \[\ n-\biggl( 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}\biggr)\approx n-\log n.\]
Permutációk paritása
| lépések száma | |||
|
|||
|
|||
|
|||
| páros sok metszéspont | páratlan sok metszéspont |
| páros sok inverzió | páratlan sok inverzió |
| páros sok lépés | páratlan sok lépés |
| a kezdő játékos nyer | a második játékos nyer |
| páros sok transzpozíció | páratlan sok transzpozíció |
| \( n-c(\pi)\ \) páros | \( n-c(\pi)\ \) páratlan |
| páros permutáció | páratlan permutáció |
Inverziók
|
|||
|
|||
Következmény
- A minimális lépésszám az inverziók száma.
- A megoldási stratégiánk optimális.
- Isten száma \(\ \frac{n(n-1)}{2} \).
- Az átlagos lépésszám \(\ \frac{n(n-1)}{4} \).
Előállítás hármas ciklusok szorzataként
 |
\( \pi \) |
 |
\( \pi\cdot(231) \) |
 |
\( \pi\cdot(231)\cdot(312) \) |
 |
\( \pi\cdot(231)\cdot(312)\cdot(612) \) |
 |
\( \pi\cdot(231)\cdot(312)\cdot(612)\cdot(634) \) |
| \( \pi\cdot(231)\cdot(312)\cdot(612)\cdot(634) = (56) \) |
| \( \ \implies \ \pi = (436)(216)(213)(132)(56) \) |
Tétel
Minden páros permutáció előállítható hármas ciklusok szorzataként.
Bizonyítás
Ha a kezdőállás páros, akkor ki tudom rakni a játékot. ∎
Másik bizonyítás
Elég transzpozíció-párokra igazolni:
\( (ab)(cd)=(abc)(adc)\ \) és \(\ (ab)(cb)=(acb). \) ∎
Előállítás hosszabb ciklusok szorzataként?
Tétel
Ha \(\ 2 \leq k < n\), akkor a \(\ k \ \) hosszúságú ciklusok vagy az \(\ S_n \ \) vagy az \(\ A_n \ \) csoportot generálják.
Tétel
Ha \(\ n \geq 5 \), akkor bármely \(\ \pi\in S_n\setminus\{\mathrm{id}\}\ \) permutáció esetén a \(\pi\)-vel megegyező ciklusszerkezetű permutációk vagy az \(\ S_n \ \) vagy az \(\ A_n \ \) csoportot generálják, vagyis az \(\ S_n\ \) csoportnak csak két nemtriviális normálosztója van: \(\ A_n \ \) és \(\ S_n \).
Tétel
Ha \(\ n \geq 5 \), akkor az \(\ A_n \ \) csoport egyszerű.
Összefoglalás
A permutációk játékos tanításának előnyei:
- az absztrakt fogalmak szemléltetése és „alkalmazása”
- az összefüggések önálló felfedez(tet)ésének lehetősége
- bizonyításokra való igény kialakítása
- a matematikai kutatás örömeinek megízlelése
- a matematikához való hozzáállás javulása