Algebros ir geometrijos pratybos. Informatika. Rimantas Grigutis

5 Pratybos. Keitiniai.

Apibrėžimas 1. Keitinio π ∈ S_{n} eile vadinamas toks mažiausias sveikas skaičius k ≥ 1, kad π^{k} =id_{S_{n}}.

Apibrėžimas 2. Skaičius d (π), apibrėžiamas formule d (π) = s − k , čia s - keičiami keitinyje π skaičiai, k - nepriklausomu̧ ciklu̧ skaičius, vadinamas keitinio π dekrementu.

1. Keitini̧ σ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 7 & 5 & 6 & 9 & 2 & 4 & 8 & 1 & 3 \end{matrix} ) parašykite nesikertančiais cik-

lais. Kokia keitinio σ eilė ? Lyginis ar nelyginis šis keitinys ? Raskite σ^{−1} .

2. Tegu σ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 2 & 5 & 1 & 8 & 3 & 6 & 4 & 7 & 9 \end{matrix} ) ,

τ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 1 & 5 & 4 & 7 & 2 & 6 & 8 & 9 & 3 \end{matrix} ) . Pararašykite keitinius σ, τ, σ ∘ τ, σ ∘ τ ∘

σ^{−1}, σ^{−1}, τ^{−1}, τ ∘ σ, τ ∘ σ ∘ τ^{−1} nesikertančiais ciklais. Kokios šiu̧ keitiniu̧ eilės? Lyginiai ar nelyginiai šie keitiniai ?

3. Tegu α = (1, 3, 5, 7, 9) , β = (1, 2, 6) , γ = (1, 2, 5, 3) ∈ S_{10} . Parašykite keitini̧ σ = αβγ nesikertančiu̧ ciklu̧ sandauga. Raskite σ ir σ^{−1} eiles. Lyginiai ar nelyginiai šie keitiniai ?

4. Tegu σ = (2, 4, 9, 7) (6, 4, 2, 5, 9) (1, 6) (3, 7, 6) ∈ S_{9} . Parašykite keitini̧ σ nesikertančiu̧ ciklu̧ sandauga. Raskite σ ir σ^{−1} eiles. Lyginiai ar nelyginiai šie keitiniai ?

5. Tegu τ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 7 & 2 & 11 & 4 & 6 & 8 & 9 & 10 & 1 & 3 & 5 \end{matrix} ), o σ = (3, 8, 7) ∈ S_{11} .

Pararašykite keitinius σ, τ, σ∘τ, σ∘τ ∘σ^{−1}, σ^{−1}, τ^{−1}, τ ∘σ, τ ∘σ∘τ^{−1} nesikertančiais ciklais. Kokios šiu̧ keitiniu̧ eilės? Lyginiai ar nelyginiai šie keitiniai ?

6. I̧rodykite, kad ord_{S_{n}} (σ) = ord_{S_{n}} (τ ∘ σ ∘ τ^{−1}) su visais σ, τ ∈ S_{n} .

7. I̧rodykite, kad grupėje S_{10} yra 10, 12, 14 eilės keitiniai , bet nėra 11 ir 13 eiliu̧ keitiniu̧ .

8. Keitinio π dekrementas d (π) = d .

1) I̧rodykite, kad signπ = (−1)^{d} .

2) I̧rodykite, kad keitini̧ π galima reikšti d transpoziciju̧ sandauga.

3) I̧rodykite, kad keitini̧ π negalima reikšti mažiau kaip d transpoziciju̧ sandauga.

9. I̧rodykite, kad bet kuri̧ S_{n} keitini̧ galima reikšti transpoziciju̧ (1, 2) , (1, 3) , ..., (1, n) sandauga.

10. I̧rodykite, kad bet kuri̧ S_{n} keitini̧ galima reikšti transpoziciju̧ (1, 2) , (2, 3) , ..., (n − 1, n) sandauga.

11. I̧rodykite, kad bet kuri̧ A_{n} keitini̧ galima reikšti keitiniu̧ {(i, j, k) |1 ≤ i, j, k ≤ n} sandauga.

12. Kiek grupėje S_{100} ciklu̧, kuriu̧ ilgis 100 ?

13. I̧rodykite, kad keitinio π = (1, 2, ..., 100) ∈ S_{100} 12-asis laipsnis π^{12} yra keturiu̧ 25 -iu̧ ilgio ciklu̧ sandauga.

14. Kiek yra 2 -osios eilės keitiniu̧ iš S_{10}? Keliuose iš ju̧ yra lygiai 6 inversijos?

Žaidimas ”15”. Kiekvienai ”15” lentos pozicijai

i_{1} i_{2} i_{3} i_{4} i_{5} i_{6} i_{7} i_{8} i_{9} i_{10} i_{11} i_{12} i_{13} i_{14} i_{15} i_{16} ,

čia visi i_{1}, ...i_{16} skirtingi iš {1, ..., 15, 16} ( skaičiumi 16 pažymėtas langelis yra tuščias), priskirsime keitini̧

( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ i_{1} & i_{2} & i_{3} & i_{4} & i_{5} & i_{6} & i_{7} & i_{8} & i_{9} & i_{10} & i_{11} & i_{12} & i_{13} & i_{14} & i_{15} & i_{16} \end{matrix} ) .

Tuo atveju, kai i_{16} = 16, sakysime, kad lentelė standartinė. Standartinȩ lentelȩ galima sutapatinti ir su keitiniu iš S_{15} :

( \begin{matrix}1 & ⋯ & 15 & 16 \\ i_{1} & ⋯ & i_{15} & 16 \end{matrix} ) = ( \begin{matrix}1 & ⋯ & 15 \\ i_{1} & ⋯ & i_{15} \end{matrix} ) .

Kiekvienam galimam ėjimui

\begin{aligned}( & \begin{matrix}1 & 2 & ⋯ & i & ⋯ & j & ⋯ & 16 \\ a_{1} & a_{2} & ⋯ & 16 & ⋯ & a_{j} & ⋯ & a_{16} \end{matrix} & ) \\ & ∥ \\ & π \end{aligned} ⇝ \begin{aligned}( & \begin{matrix}1 & 2 & ⋯ & i & ⋯ & j & ⋯ & 16 \\ a_{1} & a_{2} & ⋯ & a_{j} & ⋯ & 16 & ⋯ & a_{16} \end{matrix} & ) \\ & ∥ \\ & π_{1} \end{aligned}

priskirsime lygybȩ

π = π_{1} ∘ (a_{j}, 16) .

Norint laimėti ši̧ žaidima̧, reikia per baigtini̧ ėjimu̧ skaičiu̧ iš pozicijos

i_{1} i_{2} i_{3} i_{4} i_{5} i_{6} i_{7} i_{8} i_{9} i_{10} i_{11} i_{12} i_{13} i_{14} i_{15} i_{16} pereiti prie pradinės lentelės 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 , t.y. reikia

rasti tokius n_{1}, ..., n_{s}, kad

π ∘ (n_{1}, 16) ∘ ⋯ ∘ (n_{s}, 16) =id_{S_{16}}.

\underline{Uždaviniai}.

15.1. I̧rodykite, jeigu standartinė lentelė laiminga, tai ja̧ atitinkantis keitinys yra lyginis..

Patarimas. Žiūrėkite i̧ žaidimo lenta̧ kaip i̧ matrica̧ ir kiekvienam ten esančiam skaičiui priskirkite jo koordinates {i, j} , 1 ≤ i, j ≤ 4. Stebėkite kaip kis tuščio langelio (skaičius 16 ) koordinčiu̧ suma i+j atlikus ėjima̧. Ir pagaliau, i̧sitikinkite, kad norint pereiti nuo standartinės lentos prie pirminės reiks lyginio ėjimu̧ skaičiaus.

15.2. I̧rodykite, kad iš keitinius (1, 2, 3) , (1, 2, 4) , (1, 2, 5) , ..., (1, 2, 15) atitinkančiu̧ poziciju̧ galima laimėti žaidima̧.

Patarimas. Parodykite, kad galima tokia ėjimu̧ seka:

( \begin{matrix}1 & 2 & ⋯ & k & ⋯ & 16 \\ 2 & k & ⋯ & 1 & ⋯ & 16 \end{matrix} ) ⇝^{(1)} ( \begin{matrix}1 & 2 & 3 & ⋯ & j & ⋯ & 16 \\ 2 & k & 1 & ⋯ & 16 & ⋯ & a_{16} \end{matrix} ) ⇝^{(1)}

( \begin{matrix}1 & 2 & 3 & ⋯ & 7 & ⋯ & 16 \\ 2 & k & 1 & ⋯ & 16 & ⋯ & b_{16} \end{matrix} ) ⇝ ( \begin{matrix}1 & 2 & 3 & ⋯ & 7 & ⋯ & 16 \\ 2 & 16 & k & ⋯ & 1 & ⋯ & c_{16} \end{matrix} ) ⇝

( \begin{matrix}1 & 2 & 3 & ⋯ & 7 & ⋯ & 16 \\ 1 & 2 & k & ⋯ & 16 & ⋯ & a_{16} \end{matrix} ) .

(1) : pasinaudokite judėjimu grandine:

→ ↓
→ ↓ ↑ ↓
↑ → ↑ ↓
↑ ← ← ←

( tai i̧manoma, nes lenta standartinė, t.y. tuščias langelis 16 yra grandinėje). Šis judėjimas: 1) nekeičia 1 ir 2 pozicijose esančiu̧ reikšmiu̧; 2) bet kuria̧

grandinėje esančia̧ reikšmȩ galima cikliškai pastumti i̧ bet kuria̧ kita̧ grandinės vieta̧.

15.3. I̧rodykite, jeigu π_{1} ir π_{2} yra keitiniai atitinka išlošiamas pozicijas, tai ir π_{1} ∘ π_{2} yra keitinys atitinka išlošiama̧ pozicija̧.

Patarimas. Pakanka nagrinėti standartines pozicijas.

15.4. I̧rodykite, kad bet kuri̧ lygini̧ keitini̧ iš S_{15} galima reikšti ciklu̧ (1, 2, 3) , (1, 2, 4) , (1, 2, 5) , ..., (1, 2, 15) sandauga. Patarimas. Parašykite lygini̧ keitini̧ π transpoziciju̧ sandauga

π = δ_{1}δ_{2} ⋯ δ_{2k−1}δ_{2k} =
(δ_{1}σσδ_{2}) (δ_{3}σσδ_{4}) ⋯ (δ_{2k−1}σσδ_{2k}) =
(δ_{1}σ) (σδ_{2}) (δ_{3}σ) (σδ_{4}) ⋯ (δ_{2k−1}σ) (σδ_{2k})

ir pasinaudokite

1) (1, 2) ∘ (1, 2) =id_{S_{15}};

2) (1, 2) ∘ (i, j) = (1, 2, j) ∘ (1, 2, i) ∘ (1, 2, i) ∘ (1, 2, j) , jei i, j > 2;

3) (1, 2) ∘ (1, j) = (2, j) ∘ (1, 2) = (1, 2, j) , jei j > 2;

4) (1, 2) ∘ (2, j) = (1, j) ∘ (1, 2) = (1, 2, j) , jei j > 2.

15.5. Išreikškite ciklu̧ (1, 2, 3) , (1, 2, 4) , (1, 2, 5) , ..., (1, 2, 15) sandauga šiuos keitinius:

1) π_{1} = (1, 2, 3) (7, 5) (4, 6, 9, 8) ;

2) π_{2} = (1, 2, 3, 4) (8, 7, 5, 6) .

15.6. Ar galima laimėti ”15” žaidima̧ iš šiu̧ poziciju̧;

1) \begin{matrix}8 & 7 & 6 & 5 \\ 1 & 2 & 4 & 3 \\ 13 & 15 & 11 & 10 \\ 14 & 12 & 9 \end{matrix} ; 2) \begin{matrix}6 & 3 & 4 & 5 \\ 2 & 1 & 15 & 10 \\ 13 & 12 & 11 & 14 \\ 9 & 8 & 7 \end{matrix} ?

Jeigu galima, kaip laimėti?