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

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

No.2 回答者： shushou 回答日時： 2001/07/29 03:55

中高校生向けではありませんが。

これは置換という群に関する問題だと思います。
２ｎ枚のトランプの最初の状態を上から順に
1,2,3,4,......,2n
と表現すると、これを
1,n+1,2,n+2,3,n+3,4,......,n,2n
と置換しているのだと考えるのです。
すなわち、
左から2k-1番目の数字をkに置き換え、
左から2k番目の数字をn+kに置き換える、
という置換です。
この置換を何回か繰り返して、元の状態
1,2,3,4,......,2n
に戻るかということですが、うれしいことに
絶対に戻ってくれます。
置換群のことを知っていれば
置換群の要素の個数は有限個であることから、
このことは、さもありなん、まあ当然かな、と思えてしまえます。
もしも置換とか群のことをご存知でないなら
代数学の本の最初のほうを見てみてくださいね。

また、この現象はトランプの枚数が偶数である必要はありません。
2n+1枚のときでも、上からn+1枚を前半、のこりn枚を後半として
同じように何回かシャッフルすると元に戻ります。
さらにさらにすごいことに、どんなシャッフルの仕方でも
何回かやると元に戻るんです！
つまり、たとえば「後ろの２枚を１枚目と２枚目の間に入れる」
という変則的なシャッフルでも元に戻ります。
６枚でやってみましょう。
123456→156234→134562→162345→145623→123456
という風に。（７枚だと元に戻るのははっきり言って当たり前。）
以上のことは、全て置換群の考えで説明できます（多分）。

シャッフルの回数については、よく分かりません。
左から2k-1番目の数字をkに置き換え、
左から2k番目の数字をn+kに置き換える、
という置換が生成する部分群の要素の個数をしらべればいいのでしょうが・・・。

この回答への補足

回答ありがとうございます。
　やはり群が出てきてしまいましたか。私は大学時代理系だったのですが、数学は苦手で、群とか置換の勉強もしていません。もし、群でしか方針が立たないとすれば泣きながら（へたをすると退職後にでも）勉強してみたいと思います。
　むかし、ルービックキューブが流行していたときに、友人と
　「数学科の友達に聞いたんだけれどさ、ルービックキューブは群で解けるそうだぜ」「ふーん（？）」という会話をしたことを思い出しました。ちなみに、キューブはまだわたし全面きれいにはなりません。
　有限回のシャッフルで、有限枚数のトランプが元に戻りそうなのは何となく分かります。が、初歩的な質問で恐縮ですが、「無限ループ」（元の状態には戻らず、いくつかの状態を千日手してしまう）には入りこまないのですか。これも群では常識でしょうか。
　回数については、すみませんが、まさにこの問題の核心なので、
ｆ（２ｎ）＝ｍ　のｆを見つけなさいということなので、よろしくお願いします。
　他力本願ですみません。受験生はみならっちゃダメだよ。

補足日時：2001/07/29 09:08

No.1 回答者： taropoo 回答日時： 2001/07/29 00:03

枚数が2^jの場合だけ、しかも指針だけですが。

シャッフルを関数と捉えます。即ちk番目のカードがfj(k)に移されるとします。即ち
　　　　fj(k) = { 2k-1　　(k≦j)
　　　　　　　　{ 2(k-j)　(k>j)　　　　　　　　(*)
です。こうすると示すべき問題は
　　　　fj^j(k) = fj(fj(...fj(k)...)) = k　　　　(**)
という式に帰着できます。

1)j=1のとき
　　　　f1(k) = { 1　(k=1)
　　　　　　　　{ 2　(k=2)
よってj=1の時(**)は成立する。

後は数学的帰納法により任意のjについて(**)が成り立つ事を示せば良いです。

この回答への補足

回答ありがとうございます。
申しわけありませんが、
＞　fj(k) = { 2k-1　　(k≦j)
　　　　　　{ 2(k-j)　(k>j)　
というところが、よく分かりません。たとえば、２＾３＝８ですが、
１２３４５６７８　→　１５２６３７４８　で、５番目の５はシャッフルによって２番目の位置にきています。
　ｆ３（５）＝　２　というわけですが、上の式では　５＞３　ですから
２（５－３）＝　４　となりそうなんですが。
私の理解が間違っているとは思いますが、よろしくお願いします。
　　　　　　　

補足日時：2001/07/29 08:59