Permutációs játékok
Cserélgetős játék
 |
\(\;\; \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) \) |
Előállítás transzpozíciók szorzataként
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.\]
Kétszemélyes cserélgetős játék
| lépések száma | |||
|
|||
|
|||
|
|||
Permutációk paritása
| 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ó |
Cserélgetős játék: csak szomszédokat
|
|||
|
|||
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} \).
Cserélgetős játék: hármasával
 |
\(\;\; \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) \) |
Előállítás hármas ciklusok szorzataként
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). \) ∎
Cserélgetős játék: négyesével
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ű.
Permutációs játékok
Bármely \(\; H \subseteq S_A\; \) permutációhalmaz meghatároz egy
\( \mathcal{J}=(P,L,p_0,N)\;\) egyszemélyes permutációs játékot:
- \( P=S_A,\)
- \( (p,q)\in L \iff \exists\, \pi\in H \colon\ q=p\cdot\pi, \)
- \( p_0 \in S_A \) tetszőleges kezdőállás, és
- \( N=\{ \operatorname{id}\}. \)
Cél: \(\; p_0 \cdot \pi_1 \cdot \ldots \cdot \pi_\ell = \operatorname{id},\;\) ahol \(\; \forall i\colon \pi_i\in H\).
Nyilván \(\; p_0 \cdot \pi_1 \cdot \ldots \cdot \pi_\ell = \operatorname{id}\iff p_0 = \pi_\ell^{-1} \cdot \ldots \cdot \pi_1^{-1},\;\) tehát akkor és csak akkor létezik nyerő stratégia, ha \( p_0 \) benne van a \( H \) halmaz által generált permutációcsoportban.
A Rubik-kocka
iamthecu.be
A csúcskockák orientációja
| 0 | 1 | 2 |
| 
| 
|
| 
| 
|
A csúcskockák helyzete leírható egy \(\; (\sigma, \mathbf{c} ) \in S_8 \times \mathbb{Z}_3^8 \;\) párral.
Tétel
A \(\; (\sigma, \mathbf{c} ) \in S_8 \times \mathbb{Z}_3^8 \;\) csúcsállapot akkor és csak akkor érhető el a kezdőállásból, ha \(\; c_1 + \cdots + c_8 = 0\;\).
Következmény
A mini Rubik-kocka kezdőállásból elérhető állapotainak száma \[ \frac{1}{3} \cdot 8! \cdot 3^8 \ = \ 88\,179\,840.\]
Az élkockák orientációja
Az élkockák helyzete leírható egy \(\; (\tau, \mathbf{e} ) \in S_{12} \times \mathbb{Z}_2^{12} \;\) párral, így a teljes kocka állapota leírható egy négyessel: \[ (\sigma, \tau, \mathbf{c}, \mathbf{e} ) \in S_8 \times S_{12} \times \mathbb{Z}_3^8 \times \mathbb{Z}_2^{12}. \]
Tétel
A \(\; (\sigma, \tau, \mathbf{c}, \mathbf{e} ) \in S_8 \times S_{12} \times \mathbb{Z}_3^8 \times \mathbb{Z}_2^{12} \;\) állapot akkor és csak akkor érhető el a kezdőállásból, ha \( \sigma \) és \( \tau \) azonos paritású, és \(\; c_1 + \cdots + c_8 = 0\;\), \(\; e_1 + \cdots + e_{12} = 0\;\).
Következmény
A Rubik-kocka kezdőállásból elérhető állapotainak száma \[ \frac{1}{12} \cdot 8! \cdot 12! \cdot 3^8 \cdot 2^{12} \ = \ 43\,252\,003\,274\, 489\,856\,000.\]
Isten száma
| játék | állások száma | Isten száma |
|---|---|---|
| tizenötös játék | \( 10\,461\,394\,944\,000 \) | \( 43 \ (80) \) |
| mini Rubik-kocka | \( 88\,179\,840 \) | \( 11 \ (14) \) |
| Rubik-kocka | \( 43\,252\,003\,274\, 489\,856\,000 \) | \( 20 \ (26) \) |
| alsó becslés | felső becslés | |
|---|---|---|
| 1979 Singmaster | 18 | 277 |
| 1981 Thistlethwaite | 18 | 52 |
| 1990 Kloosterman | 18 | 42 |
| ⋮ | ⋮ | ⋮ |
| 1995 Reid | 20 | 29 |
| ⋮ | ⋮ | ⋮ |
| 2010 Rokicki, Kociemba, Davidson, Dethridge | 20 | 20 |
Forrás: cube20.org