ショーちゃんの気まぐれブログ

気まぐれに思ったことを気まぐれに

互換と互換分解の方法

前回の記事の続きです。
https://g44song38ke.hatenablog.jp/entry/2019/06/19/180648

互換

2つの数を入れ替えるだけの置換のことを、「互換」という。

i と j だけが入れ替わる互換のことを( i, j ) と書く。

互換分解

全ての置換は、「互換の合成」で表すことができる。

置換を「互換の合成」で表すには、次のようにする。

aをn次の置換とする。

1,2,・・・n のうち、

a(i)=i となる自然数iたちを、「グループ0」と呼ぶことにする。

「グループ0」に入ってない数i_{1}を適当に選ぶ。

(m_{1}a)(i_{1})=i_{1} となる自然数m_{1}が存在する。

i_{1},a(i_{1}),(2a)(i_{1}),\cdots ((m_{1}-1)a)(i_{1}) を「グループ1」とする。

「グループ0」と「グループ1」に入ってない数i_{2}を適当に選ぶ。

(m_{2}a)(i_{2})=i_{2}となる自然数m_{2}が存在する。

i_{2},a(i_{2}),(2a)(i_{2}),\cdots ((m_{2}-1)a)(i_{2}) を「グループ2」とする。

以下、同様にして「グループ」を作っていき、

「グループ k 」まで作ると、残ってる数がなくなったとする。

1以上k以下の自然数dについて、

i_{d}a(i_{d})を入れ替える互換をL_{d,0}

(pa)(i_{d})((p+1)a)(i_{d})を入れ替える互換をL_{d,p}とする。

それらの合成L_{d,0}+L_{d,1}+\cdots L_{d,m_{d}-2}R_{d}と定める。

そして、R_{1}+R_{2}+\cdots R_{k} を考えると、実は、これがaと同じになっているのである。

こうして、置換を「互換の合成」の形で表すことができた。

この作業のことを「互換分解」と呼ぶ。

練習問題

よく分からない人も多いと思うので、実際に置換を「互換の合成」の形に分解する感覚を掴んでみよう。

9次の置換a,b,c,d,e,f,g,hがある。

それぞれの置換によって、1,2,・・・9がどこに行くのかを次のような表にして表した。

1 2 3 4 5 6 7 8 9
a 1 4 7 2 6 3 9 8 5
b 2 5 9 7 1 6 3 4 8
c 3 7 2 6 9 4 5 1 8
d 8 5 1 3 2 9 7 4 6
e 4 3 2 7 8 1 6 9 5
f 9 4 2 3 7 6 8 5 1
g 8 4 3 9 1 7 2 6 5
h 2 8 1 3 9 7 5 6 4

この時、置換a,b,c,d,e,f,g,h を「互換の合成」の形に分解せよ。

ぜひやってみてください。

巡回定理のお話

前回の記事の続きです。
https://g44song38ke.hatenablog.jp/entry/2019/06/19/002335

巡回定理

置換のm倍

置換とは、A = {1,2,3,・・・n} としたときの、「AからAへの写像」であった。
よって、その「合成」を考えることができる。

置換a を自分自身(置換a )と合成させた置換a+a のことを、2a と書く。

さらに、置換2a と置換a を合成させた置換のことを、3aと書き、
置換3a と置換a を合成させた置換のことを、4aと書く。

以下、同じようにして、5a,6a,7a,・・・と書いていき、このようにして、「置換のm倍」ma を定義する。

巡回定理

aをn次の置換とする。

この時、次の定理が成り立つ。

1以上n以下の自然数 iについて、(ma)(i)=iとなる自然数mが必ず存在する。

証明してみよう。

そのような自然数mが存在しないとする。

a(i)=i_{1}\neq i とする。

置換の性質①(前回の記事参照)から、

(2a)(i)=a(i_{1})\neq a(i)=i_{1} である。

(2a)(i)=i_{2}\neq iとすると、i_{2}\neq i_{1}である。

よって、i,i_{1},i_{2}は相異なる数である。

さらに、(3a)(i)=a(i_{2})\neq a(i)=i_{1} であり、

(3a)(i)=(2a)(i_{1})\neq (2a)(i)=i_{2} でもある。

よって、(3a)(i)=i_{3}\neq iとすると、i_{3}\neq i_{2}であり、i_{3}\neq i_{1} でもある。

i_{2}\neq i_{1} なので i,i_{1},i_{2},i_{3}は、相異なる数である。

以下、同じように議論していくと、i,i_{1},i_{2},\cdots i_{n}は相異なる数であることになり、
nよりたくさんの数が出てきてしまうので、矛盾する。

よって、1以上n以下の自然数 iについて、(ma)(i)=iとなる自然数mが必ず存在する。

あみだくじ問題と置換の導入!気まぐれ数学シリーズ!その6!

前回の記事の続きです。
https://g44song38ke.hatenablog.jp/entry/2019/06/17/023129

あみだくじの問題

次のような「あみだくじ」の問題を考えてみよう。

このような問題を解くのは、一筋縄ではいかない。

この問題を解くために「置換」という概念を導入しよう。

置換

A = {1,2,3,・・・,n} とする。

次の性質①を満たす、AからAへの写像σ のことを「n次の置換」という。

① i ≠ jのとき、σ(i) ≠ σ(j)

「n次の置換」全体の集合をS_{n} と書く。

例えば、「2次の置換」には、

σ(1)=1,σ(2)=2 となる写像σ と、

τ(1)=2,τ(2)=1 となる写像τ がある。

「3次の置換」には、

a(1)=1,a(2)=2,a(3)=3 となる写像a と、

b(1)=2,b(2)=1,b(3)=3 となる写像b と、

c(1)=3,c(2)=2,c(3)=1 となる写像c と、

d(1)=1,d(2)=3,d(3)=2 となる写像d と、

e(1)=2,e(2)=3,e(3)=1 となる写像e と、

f(1)=3,f(2)=1,f(3)=2 となる写像f がある。


置換の符号

n次の置換a に対して、次のようにして、符号(プラスマイナス)を定義する。

2 以上 n 以下の自然数 k に対して、F_{k}(a)という整数を

F_{k}(a)=(a(k)-a(k-1))(a(k)-a(k-2))\cdots(a(k)-a(1))

というように定める。

そして、F_{n}(a)F_{n-1}(a)\cdots F_{2}(a)=G(a)

として、G(a) を定める。

このG(a)の符号(プラスマイナス)を、「置換aの符号」として定めるのである。

この符号がどのような意味を持ち、どのようにして、あみだくじの問題を解決させるのかは、また次回話すことにしよう。

あみだくじ問題解決への道はなかなか遠い。。。
頑張らねば(汗)

ジャンケンと写像!気まぐれ数学シリーズその5!

写像

「〇〇を足す」の計算

10という数に「5を足す」と、15になる。
その15にさらに「7を足す」と、22になる。

一方、10という数に「12を足す」と、22になる。

つまり、10に「5を足してから7を足す」という計算の結果と、10に「12を足す」という計算の結果は同じなのである。

このことを次のように=を使って表す。

「10という数に5を足して7を足す」=「10という数に12を足す」

さらに、10以外の全ての数においても、「5を足してから7を足す」という計算の結果と、「12を足す」という計算の結果は同じになる。

そのため、先ほどの=を使った式から「10という数に」という言葉を抜いても、その式は意味を持つことになる。

その式は

「5を足してから7を足す」=「12を足す」

という風になる。

ここで、「5を足してから7を足す」と言う計算は、「5を足す」という計算と「7を足す」という計算を合わせたものだから、

「5を足す」+「7を足す」

と表現することにする。

そうすると、

「5を足す」+「7を足す」=「12を足す」

という式が出来上がる。

同じようにして、

「1を足す」+「2を足す」=「3を足す」

「10を足す」+「3を引く」=「7を足す」

のような式も出来上がる。

文字式を使うと、

「a を足す」+「b を足す」=「a+b を足す」

という式になる。

このようにして、数ではない「〇〇を足す」という言葉についての足し算が作れたのである。

このような「数以外のもの」についての「計算」を構成する方法を考えたい。

ジャンケンの計算

ジャンケンにおいて、「グー」に勝つのは「パー」である。
また、「パー」に勝つのは「チョキ」である。

一方、「グー」に負けるのは「チョキ」である。

よって、「グー」に勝つものに勝つものは、「グー」に負けるものということが分かる。

このことを次のようにして、=を使った式で表す。

「グーに勝つものに勝つもの」=「グーに負けるもの」

また、「チョキ」に勝つものに勝つもの(パー)は、「チョキ」に負けるものである。
さらに、「パー」に勝つものに勝つもの(グー)は、「パー」に負けるものである。

よって、先ほどの=を使った式の「グーに」という部分を「チョキに」「パーに」に変えても良いことが分かる。

このことから、先ほどの式から「グーに」という部分を抜いて、

「勝つものに勝つもの」=「負けるもの」

という式にしても、この式は意味を持つことになる。

さらに、「勝つものに勝つもの」という言葉を、「勝つもの」+「勝つもの」というように表現すると、

「勝つもの」+「勝つもの」=「負けるもの」

という式ができる。

同じように考えると、

「負けるもの」+「負けるもの」=「勝つもの」

「勝つもの」+「負けるもの」=「同じもの」

「負けるもの」+「勝つもの」=「同じもの」

という式などができる。

このようにして、「勝つもの」「負けるもの」「同じもの」という言葉についての足し算ができたのである。

では、この「勝つもの」「負けるもの」「同じもの」とは、一体「どういうもの」なのだろうか?

その答えは、ズバリ「写像」というものである。

写像

先ほどのジャンケンの計算の話を数学的な表現を使って説明しよう。

x を「グー」「チョキ」「パー」のいずれかとする。

x に勝つものを、a(x) と表し、x に負けるものを、b(x) と表す。
また、x と同じもの(x なのだが)を、c(x) と表す。

このとき、
「(グー、チョキ、パーに)勝つものに勝つもの」=「(グー、チョキ、パーに)負けるもの」
だから、

a(a(x))=b(x)

という式が成り立つ。

a(a(x))は、x に勝つものである a(x) に勝つものを表しているのである。

ここで、a(a(x)) のことを、(a+a)(x)と表すことにする。

すると、

(a+a)(x)=b(x)

という式になる。

x には「グー」を代入しても「チョキ」を代入しても「パー」を代入しても大丈夫である。

このとき、a+a と b は同じ「写像」であるといい、

a+a = b

という風に書く。

この a、b が先ほどの説明に出てきた「勝つもの」「負けるもの」なのである。

よく分からないという人も多いと思うが、要するに、「写像」という新しい概念なのである。

では、その「写像」というものを、定義してみよう。

写像の定義

A,B を集合とする。

Aのそれぞれの元を、Bの元に対応させることを「AからBへの写像」という。

Aの元 x が写像f で対応するBの元を、f(x) と書く。

f(x)=g(x)

という式が、x にAのどの元を代入しても成り立つとき、
f とg は同じ写像であるといい、f=g と書く。

また、f(g(x)) のことを、(f⚪︎g)(x) や(f+g)(x) などと書き、写像f と写像g の合成という。

先ほどのジャンケンの話では、A = B = {グー、チョキ、パー}である。

写像の計算

A = B = {グー、チョキ、パー} とする。

写像a を「勝つものを対応させる」写像
写像b を「負けるものを対応させる」写像
写像c を「同じものを対応させる」写像とする。

この写像たちの合成を考えると、次の表のようになる。

+ a b c
a b c a
b c a b
c a b c

これは「群」と呼ばれる構造をもつことになる。
「群」の話はまた後でしましょう。

また、AからBへの写像はこれだけではない。

写像d を「グーはチョキに、チョキはグーに、パーはパーに対応させる」写像

写像e を「グーはグーに、チョキはパーに、パーはチョキに対応させる」写像

写像f を「グーはパーに、チョキはチョキに、パーはグーに対応させる」写像

とすると、写像a,b,c,d,e,f の合成はどのようになるだろうか?

皆さんにぜひ考えてみてもらいたい。

それでは、今日はこの辺で。

トランプの美しい性質

パーフェクトシャッフル

トランプの世界において、「パーフェクトシャッフル」と呼ばれるシャッフルがある。

それは、「リフルシャッフル」というトランプを2つの山に分けて端同士を交互に噛み合わせるシャッフルを正確に8回行えば、トランプは「元の状態に戻る」というものである。

このシャッフルは、トランプのマジックでよく使われるそうで、マジシャンの人なら知らない人はいないのだそうだ。

本当に戻るのか?

本当に戻るのか検証してみよう。

上からn番目にあるカードが、「リフルシャッフル」1回によって、上から何番目に来るのかを表にしてみた。

1 1
2 27
3 2
4 28
5 3
6 29
7 4
8 30
9 5
10 31
11 6
12 32
13 7
14 33
15 8
16 34
17 9
18 35
19 10
20 36
21 11
22 37
23 12
24 38
25 13
26 39
27 14
28 40
29 15
30 41
31 16
32 42
33 17
34 43
35 18
36 44
37 19
38 45
39 20
40 46
41 21
42 47
43 22
44 48
45 23
46 49
47 24
48 50
49 25
50 51
51 26
52 52

1番上のカードと1番下のカードはずっと同じ場所だから、8回のシャッフルで元の場所に戻るのは当然である。

では、上から2番目にあるカードが「リフルシャッフル」8回でどこに行くのか確認しよう。

1回目のシャッフルで、そのカードは上から27番目に来る。2回目のシャッフルでは、上から14番目に、3回目では33番目に、4回目では17番目に、5回目では9番目に、6回目では5番目に、7回目では3番目に、そして、8回目では、上から2番目に来る。
つまり、元に戻ったのである。

分かりやすく、矢印で表現すると

2→27→14→33→17→9→5→3→2

となる。

さて、上から2番目のカードが元に戻ることは分かったが、実は、上から27、14、33、17、9、5、3番目のカードも元に戻るのである。

先ほどの矢印の表現を、27を頭にして考えてみると、

27→14→33→17→9→5→3→2→27

となり、27でも、シャッフルを8回すれば元に戻るのである。

同じようにして考えると、14、33、17、9、5、3番目のカードが元に戻ることもすぐ分かる。

よって、あと検証すべきなのは、この矢印のループの中に入ってない数である。

上から4番目のカードが、8回のシャッフルでどこに行くのかを矢印で表すと、次のようになる。

4→28→40→46→49→25→13→7→4

よって、先ほどと同じように考えれば、4、28、40、46、49、25、13、7は8回のシャッフルで元に戻るのである。

この要領で、他の数の検証もしていくと、

6→29→15→8→30→41→21→11→6

10→31→16→34→43→22→37→19→10

12→32→42→47→24→38→45→23→12

18→35→18 (2回で元に戻るので、8回でも当然元に戻る)

20→36→44→48→50→51→26→39→20

これで、2から51までの全ての数が8回のシャッフルで元に戻ることが分かった。

このようにして、「パーフェクトシャッフル」が成り立つのである。

いいネタ思いつかない2

そもそも僕の記事をみんなはどのくらい読んでくれてるんだろ?

読んだ人は、どのくらい内容を理解できているんだろ?

そんなことを考えながら、ブログを書く。

ガロア理論などを説明できたらいいなぁ。