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

質問

この問題は私が高校生の時に「発見」したものですが、いまだに解けなくて困っています。どなたか数学に強い方解いて下さい。できれば、中・高校生にも分かる解法でお願いします。
○偶数（２ｎ）枚のトランプがある。これを前半と後半の２つに分け、１枚ずつ互い違いになるように何回かシャッフルすると、最初にトランプのカードが並んでいた状態に戻るようである。　必ず戻るのか、証明せよ。　もしそうなら、トランプの枚数２ｎと、戻るのに要するシャッフルの回数ｍとの関係はどうなるか。
○少し説明します。
・トランプ６枚のとき
　ＡＢＣＤＥＦ＞ＡＤＢＥＣＦ＞ＡＥＤＣＢＦ＞ＡＣＥＢＤＦ＞ＡＢＣＤＥＦ　で、４回で元に戻ります。最初のカード（Ａ）と最後のカード（この場合はＦ）はその位置が変わりません。２回シャッフルしたときにアンコの部分がちょうど逆転していて、４回で元に戻ることが予想できます。
・トランプ８枚のとき
　ＡＢＣＤＥＦＧＨ＞ＡＥＢＦＣＧＤＨ＞ＡＣＥＧＢＤＦＨ＞ＡＢＣＤＥＦＧＨ　で、３回で元に戻ります。回数は６枚のときより少なくなりました。
・トランプ１０枚のとき
　ＡＢＣＤＥＦＧＨＩＪ＞ＡＦＢＧＣＨＤＩＥＪ＞ＡＨＦＤＢＩＧＥＣＪ＞ＡＩＨＧＦＥＤＣＢＪ＞ＡＥＩＤＨＣＧＢＦＪ＞ＡＣＥＧＩＢＤＦＨＪ＞ＡＢＣＤＥＦＧＨＩＪ　　で、６回で元に戻ります。このときも、３回シャッフルしたときに中身の部分が逆転しています。
・いろいろやってみると、（１）おおよそ、枚数２ｎが増えるほど、元に戻るまでのシャッフルの回数ｍは増加する傾向がある。（２）しかし、２ｎが２の累乗（４，８，１６・・・）のときには回数が減るようである。　ということは分かっているのですが・・・・。どなたかよろしくお願いします。

回答No.9

shushou

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
という例外も・・・

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

お礼

回答していただき、ありがとうございます。
　私は紙と鉛筆でしたが、さすがに計算機でやるとデータがすぐにたくさん得られて、自然現象に対するようなアプローチができますね。
　なにやら、素数とか、２の累乗とか、素因数分解とかが絡んでくるのでしょうか。前の方へも書きましたが、私このあと出張しますので、きちんとレスができなくて申しわけありません。