剰余計算の調査より

 投稿者：GAIﾒｰﾙ  投稿日：2008年12月25日(木)15時23分30秒
  数学に詳しい方は以下のことは明白なことであるでしょうが、私にとっては大発見でした。
以前
トランプのシャッフルに興味があったとき、次のことを調べていました。
カード（2n枚）でインのリフルシャッフルをしたとき、
＜いま、カードが ２ｎ枚
ａ1、ａ2、・・・、ａｎ、ｂ1、ｂ2、・・・、ｂｎ
あるとき、その順序を並べ替えて、
ｂ1、ａ1、ｂ2、ａ2、・・・・・・・・、ｂｎ、ａｎ
となるとき、
２ｎ 枚のカードが「インでリフルシャッフル」されたということにする。＞

これについて調べていくと（２～１００枚で調査）

枚数 同順復元回数 逆順復元回数 　 　枚数 同順復元回数 逆順復元回数
２   ２           １           　 　５２ ５２         ２６
４   ４           ２           　 　５４ ２０
６   ３     　 　                 　５６ １８           ９
８   ６           ３           　 　５８ ５８         ２９
１０ １０         ５           　 　６０ ６０         ３０
１２ １２         ６           　 　６２   ６
１４   ４ 　                   　 　６４ １２           ６
１６   ８         ４           　 　６６ ６６         ３３
１８ １８         ９           　 　６８ ２２
２０   ６ 　                   　 　７０ ３５
２２ １１                   　 　 　７２   ９
２４ ２０       １０           　 　７４ ２０
２６ １８         ９           　 　７６ ３０
２８ ２８       １４           　 　７８ ３９
３０   ５ 　                   　 　８０ ５４         ２７
３２ １０         ５           　　 ８２ ８２         ４１
３４ １２ 　                   　 　８４   ８
３６ ３６       １８           　 　８６ ２８
３８ １２ 　                   　 　８８ １１
４０ ２０       １０           　 　９０ １２
４２ １４         ７           　 　９２ １０
４４ １２ 　 　                   　９４ ３６
４６ ２３ 　 　                   　９６ ４８         ２４
４８ ２１ 　 　                   　９８ ３０         １５
５０ 　８ 　 　                 　１００1００  　     ５０

なる調査結果を得ていました。

このことから、トランプ（５２枚）で
アウトのリフルシャッフル（元のトップとボトムを常に再びリフル後のトップとボトムにする。）をすれば、５２枚のアウトシャッフル＝５０枚のインシャッフルに同じなので、８回
で元に戻ることが起きることになる。

ところでここに出てくる数字がランダムに並んでいくことに不思議さを感じていました。
今度、作成して頂いたa^n(mod k)を計算して表を作成して、眺めていてある関係があることに気づきました。

この同順復元回数が
a=2,k=カードの枚数＋１で計算させたとき、余りの値が１を最初にとる時のｎに対応した。
＜例＞
カード５２枚なら
　２＾ｎ≡１（MOD53)
なる最小のｎが同順復元回数になっていた。
また
　２＾ｎ≡５２　（MOD53)
なる最小ｎが逆順復元回数を知らせる。

トランプシャッフルと剰余が思わぬところで繋がったことにさらに不思議さが深まりました 		 

Re: 剰余計算の調査より

 投稿者：山中和義  投稿日：2008年12月25日(木)16時50分57秒
  > No.198[元記事へ]

GAIさんへのお返事です。

> カード５２枚なら
> 　２＾ｎ≡１（MOD53)
> なる最小のｎが同順復元回数になっていた。
> また
> 　２＾ｎ≡５２　（MOD53)
> なる最小ｎが逆順復元回数を知らせる。



１回のシャッフルでカードkが現れる位置をf(k)は（カードkはf(k)番目にある）
　f(k)=MOD(2*k,n+1)
と表せる。

m回シャッフルを繰り返すと
f(f(f(…(f(k)))))=2*(2*(2*…(2*k mod n+1) mod n+1) mod n+1) mod n+1=2^m*k mod n+1


一覧表をつくるプログラム
!リフルシャッフル

!n枚のカードを1,2,3,…,n-1,nに並べる。
!１回のシャッフルでカードkが現れる位置をf(k)と表す。（カードkはf(k)番目にある）
DEF f(k)=MOD(2*k,n+1)

FOR n=2 TO 100 STEP 2 !偶数
   PRINT USING "### 枚：":n;

   LET x=1 !カードxに着目
   LET iter=1000
   FOR m=1 TO iter !m回のシャッフル　※
      LET x=f(x) !2^m*k (mod n+1)
      !!!PRINT m;x
      IF x=n THEN PRINT USING "### 回目で逆順、":m; !逆順
      IF x=1 THEN EXIT FOR !もとに戻る
   NEXT m
   IF m>iter THEN
      PRINT USING "### 回では元に戻りません。":m
   ELSE
      PRINT USING "### 回目に元に戻る":m
   END IF

NEXT n

END


UBASICのmodinv関数を使った場合（サブルーチンは省略）
FOR n=2 TO 100 STEP 2 !偶数
   PRINT USING "### 枚：":n;

   LET iter=1000
   FOR m=1 TO iter
      LET x=modinv(2^m,n+1) !１枚目のカードの元の位置を得る
      IF x=n THEN PRINT USING "### 回目で逆順、":m; !逆順
      IF x=1 THEN EXIT FOR !もとに戻る
   NEXT m
   IF m>iter THEN
      PRINT USING "### 回では元に戻りません。":m
   ELSE
      PRINT USING "### 回目に元に戻る":m
   END IF

NEXT n
END
 

Re: 剰余計算の調査より

 投稿者：山中和義  投稿日：2008年12月26日(金)15時25分9秒
  > No.198[元記事へ]

GAIさんへのお返事です。


以前、山を使ったシャッフルがあったと思います。

「あるシャッフル方法の規則性」 > No.109 [元記事へ]


この場合は、

　LET p=3 !山の数
　DEF f(k)=MOD(p*(n-k+1),n+1)

　ただし、n=m*p（nはpの倍数）。

となるので、modpow関数またはmodinv関数を使うなら（サブルーチンは省略）
!山を使ったシャッフル
LET p=3 !山の数

FOR n=p TO 100 STEP p !pの倍数
   PRINT USING "### 枚：":n;

   LET iter=1000
   FOR m=1 TO iter
   !!!LET x=modinv((n*p)^m,n+1) !１枚目のカードの元の位置（カード番号）を得る
      LET x=modpow(n*p,m,n+1) !１番のカードの位置を得る
      IF x=n THEN PRINT USING "### 回目で逆順、":m; !逆順
      IF x=1 THEN EXIT FOR !もとに戻る
   NEXT m
   IF m>iter THEN
      PRINT USING "##### 回では元に戻りません。":m
   ELSE
      PRINT USING "### 回目に元に戻る":m
   END IF

NEXT n

END

で回数が求まると思います。 		 

戻る