逆順シャッフル四回目

逆順シャッフル

１の17乗根での巡回群

ガウスが十九歳のときに発見した正十七角形の作図と方程式の関係

多項式の根の拡大と置換

ガロア理論という見方

整数のモジュラー算術で対応

シャッフルとの関係では

逆順シャッフルとなる場合

十七角形だからmod.17

そのとき３が原始根

指数 0 1  2  3    4  5  6   7    8   9  10  11 12 13  14  15
元     1 ,3,9, 10,13,5, 15,11, 16, 14, 8,   7,  4,   12,  2,   6

ちなみに十七での原始根は

3,5,6,7,10,11,12,14

みな同じように位数16で巡回する

(フェルマーの定理でp-1でまわる)

位数8では

(1,9,13,15,16,8,4,2)

これらはすべて位数8の巡回群で

どれかひとつを連続して置換するとこれらすべての元が一巡してもとに戻る周期が八回という意味ですね

ためしに９か２かでシャッフルすればよい

じつは八の周期を持つのはこの中の

2,9,8,15

恒等置換の１とp-1があり元が巡回する正規部分群たるそれらをかけていくとマイナス１

つまりは逆順シャッフルとなる(はず)

1*9*13*15*16*8*4*2=-1

つまり九進数のシャッフルをやってつぎに１４進数シャッフルをやって、、、八回すべてやりおえると逆順となるはず

順番はかえてよい

これは全部非原始根になってる

１は恒等置換で関係ないので

注目すべきはすべて非原始根であること

位数４では

(1,13,16,4)

1*13*16*4=-1

１３か４でまわせばよい

先程の八のときの使わなかったもので

4,13

が四回目でもとに戻る

位数２では

残りの

1,16

1*16=-1 mod.17

これは当たり前か

部分群はみんなp-1の約数でまわるのでこれでよい

ちなみに原始根をすべてかけると

3*5*6*7*10*11*12*14=1

理論では平方非剰余が原始根になりうるが平方非剰余であっても原始根であるとはかぎらないという

だけどこの場合例外なくなってる

実際は根をたしあわせてその係数としそれをかけてくみあえあせる多項式

ここでは元を直接計算するから掛け算する

これらがくみあわさった多項式の根が二次式で表されるから正十七角形は解けるつまり定規とコンパスだけで作図可能。

スペルトリック再び

七枚でスペルトリック

７の乗法逆元とすべての組み合わせ
(１のところが乗法逆元で６がアンチ)

乗積表

(7) 1 2 3 4 5 6
1   1 2 3 4 5 6
2   2 4 6 1 3 5
3   3 6 2 5 1 4
4   4 1 5 2 6 3
5   5 3 1 6 4 2
6   6 5 4 3 2 1

相手のスペルが二文字のときは２の配置となるようなシャッフルをする

それは２の逆元で表から４であるとわかる

具体的には

作りたい配列

7)1 2 3 4 5 6 7
1)1 2 3 4 5 6 7
2)2 4 6 1 3 5 7
3)3 6 2 5 1 4 7
4 )4 1 5 2 6 3 7
5)5 3 1 6 4 2 7
6)6 5 4 3 2 1 7

間隔をみると
2→4
3→5
4→2
5→3

うえから一枚ずつ四ヶ所にくばって

集めるときにはうえの配置になるようにすればいい

逆に四文字なら２をシャッフルする

その逆元の配置のシャッフルする

相手が選んだ数をディールシャッフルしてからやるときは

まず逆元シャッフルでもとに戻してから

その数をかけたあとにスペルの配置のシャッフルになればよい

逆元シャッフル

２を選んだら４を

３を選んだら５を

４を選んだら２を

５を選んだら３を

シャッフルするんだ

カードのならびに対応するシャッフルの元を適切に選べばよい

また相手が選んだ数がたまたま逆元の配置に一致していればそのままでもよい

素数の枚数が必ずや一様になることを保証している

あるいは即席の演出が難しいときは魔法の言葉？を用意しておいてブランクバックカードにメッセージを綴ってもらったものをシャッフルで変換してスペルの手法で出すというのもよい

数字の配列を確認しながらできる

Mのスペルをしたかったら

MN≡1

なるN進シャッフルしてMのスペルの状態となってそれをM進シャッフル(M.spelling )すれば解読できる

演出のテクニック

２から５の間の数を指定させる

この時２や５を選んだら

２から５の「間の」数ですよといってもう一度３か４をえらばせる

３は原始元ですべてでるから都合がよい

ディールシャッフルでNM進シャッフルすると順が逆順になる問題はパケット全体をリバースシャッフルすればいいか

表向きに配り最後は相手の名前だけパケット全体を裏向きでスペルしてメッセージを解読すればいいか。

逆元の計算

乗法逆元とは

mod.pで

ax ≡1
なる元

ふつうの場合は逆数で

3* 1/3 =1

加法なら

7+(-7)=0

ですが

カードシャッフリングでの乗法逆元はアンチシャッフル

逆元の計算

ax + by =GCD(m)

ふつう
mod.pで

ax ≡1

はGCD(1)だから

ax + by =1

すなわち

ax + yp=1

さらに真ん中の符号をマイナスにしておく

例

十七枚のカードで十進のパーフェクトシャッフルをやったあとに完全にもとのならびに戻すには？

十進の乗法逆元をもとめればよい

拡張版ユークリッドのアルゴリズム

そこでつかうのが拡張版ユークリッドのアルゴリズムというもん

原理はさておいて実際には筆算で簡単にとける

逆元の求め方

10x - 17y =1

のxとyとの特別解を求めればよい

どうやるか

まず大きい方の数をかく

17

そのしたに小さい方の数をかく

17
10

大きい方から小さいほうを引けるだけ引く

その商を右にかく
17
10 1

そうしたら余りをしたにかく

17
10 1
7

またおなじように

17
10 1
7    1
3
これを余りが１になるまでやる

17
10  1
7    1

3    2
1

今度はその列の右側にしたから上に向かって0と1をかきこむ
それはきまりとなってる2

17
10  1
7    1
3    2             1
1→→→→→0

今度はそのうえに先程だした商をかけ算したものをかく

17
10  1
7    1             2
3    2  →→→1    
1→→→→→0

今度も同様にしてとなりの商とかけ算するがその結果に下の数を足した数をかきこむ

17
10  1　　　 3
7 　1→→→ 2
3    2  →→→1    
1→→→→→0

同様にして上までやる

17                5
10   1→→→3
7 　1→→→ 2
3    2  →→→1    
1→→→→→0

うえの二つの数がxyのはず

ここで検算
もとの数字とたすきにかけてみて差が１になればよい

17        \  /    5　=50
10   1   /  \    3   =51
7 　1→→→ 2
3    2  →→→1    
1→→→→→0

答えは小さい方がxで１つ大きい方がy
x=5
y=3

10*5 - 3*17 =-1?

ここでマイナス１となる場合はそれぞれ符号をかえればよい

10*(-5) -17(-3)=1

で

-5≡12  mod.17

ということに注意すると

求める答えは

10*12≡1

十二進のシャッフルをすればよい。

ステイスタック

ステイスタックの数理？

パーフェクト(ファロ)シャッフルのときに対称になるペアが保たれるという

これは

合同の計算で

mod. p

x≡p +x

であるわけで

mod.53

-1≡53-1≡52
-2≡53-2≡51
-3≡53-3≡50
-4≡53-4≡49

つまりは
1→2→4

とうごくとそれにより
52(-1)→-51(-2)→49(-4)

と符号をかえれば簡単に計算できる

53-26=27
53-27=26
53-20=33
53-33=20
53--24=29
53-29-24
53-19=44
53-44=19

足して５３になる
中心を対称におなじ距離のペアが保つわけ

これはmod. PでのN進法シャッフルではすべてそうなるか

前にやった三分割シャッフルでもそうなってた

これをつかうとちょっとしたマジックができる

足して１４になる組み合わせでペアにしてスペードにはダイヤ、ハートにはクラブといった具合に調節しておく

これを中心対称にならべておいてパーフェクトシャッフルする

もちろんファロでインでもアウトでも混ぜてよい

何回かやったらミルクビドルでペアにしてテーブルにならべる

うえの一枚を表向きにしておく

下のカードが何であるか当ててしまうことができる

いつも同じペアが保たれるのでゲスできる

あるいは一枚好きなカードの名前をいってくれという

マジシャンもこのとき好きなカードをいうという

お互いが心がけがよいとその二枚がデックのなかでくっつくという

じつは相手のいったカードのペアになるカードをいうだけでできる

これを使えば前に考察したファロのイカサマと同等のことができる

ペアにするカードの組み合わせを規則性がないようにすればいい

自分だけのペアをメモライズドしておけば。

またシャッフルについて

インのパーフェクトシャッフルとアウトのパーフェクトシャッフルをこうごにやると

七枚のカードの場合
インをやってからアウトの順番

1 2 3 4 5 6 7

ただし７は不動点で省略

i) 4 1 5 2 6 3  o)1 4 2 5 3 6

io)4 2 1 6 5 3

でわ

i)4 1 5 2 6 3

o)4 2 1 6 5 3

i)6 4 5 2 3 1

o)6 2 4 3 5 1

i)3 6 5 2 1 3

o)3 2 6 1 5 4

i)1 3 5 2 4 6

o)1 2 3 4 5 6

で全部戻るまで結局八回かかった‼
これを計算で求めると
inpfs
2^r≡x(mod.7)
outpfs
2^r  -1 ≡x(mod.5)

計算結果も
  1 2 3 4 5 6
  2 4 6 1 3 5
  3 2 6 1 5 4
  6 4 5 2 3 1
  6 2 4 3 5 1
  5 4 1 6 3 2
  4 2 1 6 5 3
  1 4 2 5 3 6
  1 2 3 4 5 6

これはカードの動きかたのポジションをあらわしてる

こんどはアウトをやってからインという順番

o)1 4 2 5 3 6
i5 1 3 4 6 2
o)5 4 1 6 3 2
i)6 5 3 4 2 1
o)6 4 5 2 3 1
i)  2 6 3 4 1 5
o )2 4 6 1 3 5
o)1 2 3 4 5 6

計算結果も

1 2 3 4 5 6
1 3 5 2 4 6
2 6 3 4 1 5
3 6 5 2 1 4
6 5 3 4 2 1
6 4 5 2 3 1
5 1 3 4 6 2
4 1 5 2 6 3
1 2 3 4 5 6

シャッフルについて３

もう少しべつの角度からデバイドのシャッフル(置換)をみてみる

普通のパーフェクトファローシャッフルは二進の置換ですから

理論上は

七枚のカードで三分割なら

3^r ≡1 (mod.7)

のrが戻る回数ですね

因みにファロー置換なら

2^r ≡1 (mod.7)なら
0)1 2 3 4 5 6 7

1)2 4 6 1 3 5 7

2)4 1 5 2 6 3 7

3)1 2 3 4 5 6 7

で三回でもどってしまう(これは７を法としたときに２が原始根でないから2^3≡1)

すべての元を３掛けて７をこえたら引けるだけひけばよい

0)1 2 3 4 5 6 7

1)3 6 2 5 1 4 7

置換表示
(1 3 2 6 4 5 )

の六回で戻るはず

ふむ

７を法として３は原始根

７は素数でp-1で６

これをカードでやるには置換のとうりにとっていけばよいか

ただしはじめは「三枚ずつ」にたばにして左から右におく

1 2 3|4 5 6| 7
それで右真ん中左という順番に「一枚ずつ」重ねていくのがいい

ただし右のパケット？は７の一枚しかないからあとは真ん中左真ん中左となる

3 6 2 |5 1 4 |7

だから７は不動点で動かない

このタイプのシャッフルではモデルとして完全に計算可能なのでなん分割でも何回でもとに戻るかは原始元かどうかできまる
元(カード)の組み合わせによってもっとはやくもとに戻るはず

講談社ブルーバックスの「素数入門」「数論入門」(ともn著者は芹沢正三さん)
には付録に位数表や指数表や素数の最小素数原始根の表があって役に立つ‼

ためしに十三枚では３進シャッフルをするには

３は１３を法として原始元でない

３回でもとに戻るはず

で実際に(13は0で不動)

1) 3 6 9 |12 2 5 |8 11  1 |4 7 10
2)9 5 1| 10 6 2 |1 7 3| 12 8 4
3)1 2 3| 4 5 6 |7 8 9 |10 11 12

循環置換の表示
(1 3 9)
(2 6 5)
(4 12 10)
(7 8 11)

で四分割のシャッフルとして実行できる。
(因みに５３だと２３と３０が四回で戻るらしいなんてのがある、多分乗法逆元でインバースの置換はリバースシャッフルなので二回でもとに戻るけどどうやったら実行できるか？)