問題の変形

剰余類で周期を求める

周期(サイクル)とは

a^r ≡1(mod.p)

となるrでありパーフェクトシャッフルならトップカードが何度かのシャッフルで周遊してまた

もとのトップにもどる(それいがいの枚数のカードも同様にして)その一巡の回数をいう

パーフェクトシャッフルとは

おなじ置換で何度かの入れ換えをやること

たとえば

六枚のカードで二進のパーフェクトシャッフルをやると
(これはin-perfect faro shuffleという)

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

という置換表示なら

実際には

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

とそれぞれが動くのであり

これを表にすると

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

これをサイクル表示で

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

で３サイクルの素なサイクルになる

循環節の長さ

1/19=

循環節なら底が１０ですが

2*10=20≡1　mod.19

から逆元もおなじ周期なはず

十九枚なら

パーフェクトシャッフルでももとめられるか

(パーフェクトファロシャッフルの底は２)

しかも対称性があるので剰余の数列が逆になるだけなので

つまり十九枚のカードでパーフェクトファロシャッフルしてもとにもどる回数がおなじと

10:[10,5,12,6,3,11,15,17,18,9,14,7,13,16,8,4,2,1]

2:  [2,4,8,16,13,7,14,9,18,17,15,11,3,6,12,5,10,1]

しかも対称性から上下にみると

10*2=20≡1
5*4=20≡1
12*8=96≡1
6*16=96≡1
13*3=39≡1
11*7=77≡1
15*14=210≡1
17*9=153≡1

と逆元のペアが全部デテルジャアリマセンカ？

ということはひとつ原始根の元をまわせればその剰余の逆置換をだしてみれば逆元が求まると

ということは逆に

ある原始元のひとつで剰余演算のうえで逆元をもとめて(拡張版ユークリッドのアルゴリズム)
前と後ろから同時に並行で剰余の数列(サイクル)を求めていけるか

いやむしろ相補性があるのでp-1の半分かp-1がでてくるまで計算すればいいことになる。

逆元の計算

乗法逆元とは

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

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

シャッフルと循環するカードの話

十三枚のカードで分割シャッフルする

循環小数とレピュニット

レピュニットとは

11111

77777

99999999

とかのおなじ数が連続する数字のこと

これがカードをシャッフルするとあらわれる周期と関係する

どういうことかというと

1111111111111

を面倒なので以下

R13というとする

シャッフルの計算で

10^13 - 1が53で割りきれれば

10^13 ≡+1 (mod. 53)

なので実際に

1-10-47-46-36-42-49-13-24-28-15-44-16-1

トランプ一組を十進でシャッフルしたら？十三回でもとにもどる

これはR13が53を因子としてもっているから

１以外の元もぜんぶモドる

じつはレピュニットの長さが十進でシャッフル(計算)したときの周期とつながる

トランプの枚数が因子とし

つまりは

1111111111111=53*79*265371653

またここから
10^13  ≡1  (mod.79)

10^13  ≡1 (mod.265371653)

もうひとつ

13を因子としてもっているレピュニットの長さはいくつか？

10^r ≡1 (mod.13)

10^r -1

の最小周期
10^6 ≡1

だから111111で六

111111=13*8547

循環小数の周期

1/p

pは素数とする

有名なシャッフルの式

a^p-1 ≡1(mod.p)

1/13

10^12≡1(mod.13)

である実際には分割シャッフルの手法で実行できるがここでは計算で

(1.10.9.12.3.4)
(2.7.5.11.6.8)

ということで循環周期は六

したがって

10^6≡1(mod.13)

因みに分割シャッフルでは三分割シャッフルでよい

また三回目には逆順となるので

10^3 ≡-1(mod.13)

つまり

10^3 +1≡0(mod.13)

つまり

1001=13*11*7

だから

10^3 +1≡0(mod.11)

10^3 +1≡0(mod.7)
だから

101,1001,10001....

こういう形の数は(名前があるのか？)

レピュニットの長さがどんな周期の素数を因子としてもっているかどうかできまるわけだ

ぜんぶおなじ周期をもっている素数が因子として集まってるわけだ‼。

シャッフルについて３

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

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

理論上は

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

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)

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