偶数枚のトランプのシャッフル

　「離散対数問題」というのは初めて聞きました。

勉強になります。ありがとうございます。

　せっかくなので、頑張ってワープロしてみます。

　動かない一番上と一番下を除いた時に、一番上（２ｎ枚ある時の上から２枚目）にあるカードが元の位置に戻る回数に着目すれば、証明できます。

　一番上と一番下を除いた２ｎ－２枚のカードで上からｍ枚目にあるカードは、
　１回のシャッフルで、
　　　　１≦ｍ≦ｎ－１のとき２ｍ枚目に、
　　　　ｎ≦ｍ≦２ｎ－２のとき２ｍ－（２ｎ－１）枚目に移動します。

　２ｍ≡２ｍ－（２ｎ－１）（mod ２ｎ－１）であることから、
　ｍ枚目のカードは、ｔ枚目（ｔは１≦ｔ≦２ｎ－２，２ｍ≡ｔ（mod ２ｎ－１）をみたす）に移動することになります。

　よって、ｋ回のシャッフルでｍ枚目のカードがｍ枚目に戻るのは、
　ｍ×２＾ｋ≡ｍ（mod ２ｎ－１）をｋが満たすときです。

　これから、２＾ｋ≡１（mod ２ｎ－１）が得られます（つまり、２ｎ－２枚の一番上が元に戻る時に、すべてのカードが元に戻るということです）。

　あと、一意性だとかこまごました処理がありますが、面倒なのでご容赦下さい。

　私が最初にこの問題を知ったのは、野崎昭宏さんのトランプの本かなにかだったと思います。その本には、「シャッフルでもとに戻る」ことと「何枚ぐらいだと何回で戻る」ということしか書かれていませんでした。で、あーでもないこーでもないと考えて、上記の結論に至ったわけです。
　ｋについて解けたらカッコいいなぁと思ってましたが、どーやら私には無理みたいですね。

　追記：「経験者」というのは、「この問題を考えた経験がある」という意味です。

neo_otackyさんの言うことが本当だとするとこれは離散対数問題

と呼ばれる問題でしょうか。これが解けると素因数分解が高速にとけて
RSA暗号が破られてしまう。と言うようなことを聞いたことがあります。
ひょっとするとこの問題は今だ誰もといたことのない未解決問題なのかも
しれません。(厳密な事はチトわかりませんが)

一番上と一番下の位置が変わらないシャッフルですよね？

ワープロするのが大変なので、結論だけ書きます。

２ｎ枚（ｎ≧２）のとき、２＾ｋ≡１（mod ２ｎ－１）
をみたす最小の自然数ｋが求める回数です。

これをｋについて解けるのかどうかは、よくわかりません。

shushouです。

まず、無限ループに陥らないか、ということですが
nagataさんのおっしゃるようにこの点は心配いりません。
群論的にもありえません。

問題の元に戻る回数ですが、
abt-594さんの非常に分かりやすい、すばらしいアイディアをもとに
basicで計算してみました。（私はbasicしか使えないんです。とほほ。）
トランプの枚数がm枚のとき、
元に戻るシャッフルの回数をf(m)とします。
まずf(2n-1)=f(2n)です。
（これはシャッフルの様子を紙に書いてみればすぐ分かります。）
なので、motsuanさんのおっしゃるように
本質的にはnが奇数の場合を考えればいいようです。
nが素数の時に結構特徴的なので。

さて、トランプの枚数が2^nのときは
f(2^n)=f(2^n-1)=n+1
となります。
これはNo.3のabt-594さんのように
Bの順位を矢印で結んで書いてくと納得できますよ。
また、
f(3)=2,f(5)=4,f(11)=10,f(13)=12,f(19)=18,f(29)=28,f(37)=36,
f(53)=52,f(59)=58,f(61)=60,f(67)=66,f(83)=82
とか
f(7)=3,f(17)=8,f(23)=11,f(41)=20,f(47)=23,f(71)=35,
f(79)=39,f(97)=48
のように、pを素数とすると
f(p)=p-1 あるいは　(p-1)/2
となることが目に付きます。
でも,
f(43)=14,f(73)=9,f(89)=11
という例外も・・・

結局、規則性はまだ分かっていません。

シャフルを行列 A で表し、ある数 ｋ で

　A^k = 1
であることを、固有多項式
　f(x) = det|xI-A| (I は単位行列、detは行列式）
が因子として x^k-1 を含むとして、示せば良いのかな
（うまく行けば証明できる）と考えました。
（高校生的にいえば
　ハミルトン-ケーリの定理を使って考えてみました）
．．．答えが出ていないので参考までに。

N×N行列 A_{N} の (m, n) 成分 (m,n = 0,1,2,...,N-1) を、
　シャフル前に n 番目にあったカードがシャフルで m 番目に移されるとき = 1
　それ以外 = 0
とします。A_{N} を行列として r 回掛けて、p 列目の成分で q 行目が 1 であれば、
r 回のシャフルで p 番目にあったカードが q 番目に移されることを表します。
具体的には、( m, n ) 成分 a_{mn} を
　a_{mn} = δ( m - 2n - floor(n/ceiling(N/2)) ( mod 2 ceiling(N/2) ) )　・・・（☆）
　（δ(x) は x = 0 のときは 1 それ以外は 0,
　　floor(x) は x を以下の最大の整数,
　　ceiling(x) は x を以上の最小の整数）
とでも表せばいいのでしょう（ちょっとカッコ悪い）。
I_{N} をN×Nの単位行列として、
　f(N,x) = det|xI_{N} - A_{N}|
これをがりがり計算機(Mathematica)で実行すると、
　f(1,x) = x -1, f(2,x) = (x -1)f(1,x) : k = 1
　f(3,x) = (x -1)(x^2-1), f(4,x) = (x -1)f(3,x) : k = 2
　f(5,x) = (x -1)(x^4-1), f(6,x) = (x -1)f(5,x) : k = 4
　f(7,x) = (x -1)(x^3-1)^2, f(8,x) = (x -1)f(7,x) : k = 3
　f(9,x) = (x -1)(x^2-1)(x^6-1), f(10,x) = (x -1)f(9,x) : k = 6
　f(11,x) = (x -1)(x^10-1), f(12,x) = (x -1)f(11,x) : k = 10
　f(13,x) = (x -1)(x^12-1), f(14,x) = (x -1)f(13,x) : k = 12
　f(15,x) = (x -1)(x^4-1)^3(x^2-1), f(16,x) = (x -1)f(15,x) : k = 4
　f(17,x) = (x -1)(x^8-1)^2, f(18,x) = (x -1)f(17,x) : k = 8
　f(19,x) = (x -1)(x^18-1), f(20,x) = (x -1)f(19,x) : k = 18
　 :
となるようです（ｋの値は実際にべき乗をとったときに単位行列になる数、
まとめ方は意図的にｋの値がでるようにまとめています）。
問題にされているのはNが偶数の場合のようですが、
奇数の場合に(x -1)を掛けただけなので
（Nが偶数の場合の最後の１枚は順番が入れ替わらないことを反映しています）、
本質的には奇数の場合を考えればよいと思います。
いまのところ私には規則性が見出せません。

>有限回のシャッフルで、有限枚数のトランプが元に戻りそうなのは何となく分かります。

が、初歩的な質問で恐縮ですが、「無限ループ」（元の状態には戻らず、いくつかの状態を千
>日手してしまう）には入りこまないのですか。これも群では常識でしょうか。

これについてお答えします。
まずシャッフルの操作は結果が一意に求まり、逆変換も一意に求まります。
これはわかりますよね。
御心配している状況は下のようなものでしょうがこれは逆変換が一意に求まる
ことに反します。つまり2つの点から矢印が入って来るような点(白い丸)があると
逆変換が一意にならないのです。

スタート
●
↓
●
↓
○←●
↓・↑
●→●

> ＞　fj(k) = { 2k-1　　(k≦j)

> 　　　　　　{ 2(k-j)　(k>j)　
> というところが、よく分かりません。

そうですね、私の勘違いでした。正しくは
　　　　fj(k) = { 2k-1　　　　　(k≦j)
　　　　　　　　{ 2(k-2^(j-1))　(k>j)　　　　　　　　(*)
ですね。失礼しました。

補足2　何度もすいません

考えやすくするために、次のようなシャッフルで考えていたのに、シャッフルの方法を題意の通りに直すのを忘れていました。

ababababababababababababababab
　　　　　　　　↓
　 a a a a a a a a a a a a a a a
　　b b b b b b b b b b b b b b b
　　　　　　　　↓
aaaaaaaaaaaaaaabbbbbbbbbbbbbbb

jun1038さんのシャッフルとは逆の操作なので
下の例のＢの順位の経路も逆になってしまっています。

補足です

下の考えをさらに拡張して、
ＢだけでなくＣやＤ…２ｎまでのそれぞれのカードの順位が元の順位に戻るまでのそれぞれのシャッフル回数を計算し、
その最小公倍数を求めればｍになりますね。
必ず戻るのかどうか証明するには、この最小公倍数が存在することを示せばよいのかもしれません。

回答では無いのですが、Ｂの順位に着目してアルゴリズムを考えてみました。

「カードが最初の状態に戻るまでのシャッフル回数」は「Ｂが再び２番目に戻るまでのシャッフル回数」
の倍数になるだろうと考えたからです。もすでにお考えになったことがあるかと思いますが、なにかのヒントになれば幸いです。

(1)－１、今のＢの順位（bとする）が偶数のとき、次のＢの順位（b'とする）は
b'= (b+2n)/2

(1)－2、今のＢの順位が奇数のとき、次のＢの順位は
b'= (b+1)/2

(2)
b= b' とする

以下これを繰り返し　b'= 2 　になるまでの回数を求める。

その数は　ｍ　の約数になるだろうと思います。

例）n=3　のとき
　　Ｂの順位は２→４→５→３→２

　　n=32　のとき
　　Ｂの順位は２→33→17→９→５→３→２