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

質問

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

回答No.12

neo_otacky · ベストアンサー

「離散対数問題」というのは初めて聞きました。勉強になります。ありがとうございます。

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

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

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

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

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

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

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

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

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

お礼

回答ありがとうございます。出張から帰ってきたら、解けていて、本当に感謝しています。頑張ってワープロ打って下さってすみません。
　ただ、私、合同≡とか、ｍｏｄなど全く知らなかったので、数学科卒の同僚に、合同やｍｏｄについてレクチャーを受けて、さらにこの解答についてのレフェリーをしてもらいました。「合っている。すばらしい着想だ。」とのことですので、また実際いくつかの場合についてやってみても合っているので、これで決まりでしょう。これで、すこしはホッとして死んでいけます。ただ悲しいかな、私自身の数学力のなさから、まだすっきりと理解はできていないので、これから時間をとって考えていきます。
　私自身のことはさておき、合同の概念さえ理解できれば、あとは自然数の世界のことなので、中高生にも十分理解できる可能が高いですね。また、neo_otackyさん以外の方々にも大変お世話になりました。この問題に関して回答してくださった全ての皆さまに感謝します。途中愚問を発したり失礼な発言があったりしてすみませんでした。
　さて、２ｎ枚のトランプについて題意のような操作（置換・シャッフル）をするときにはこの解答で良いと思いますが、回答Ｎｏ．２でshushouさんが書いているように、任意の全ての操作について何回かの操作でカードは元に戻るようです。途中の議論で明らかになったように、一意的な同じ操作を続けることによって、有限枚のカードは必ずいつかは元に戻ります。では、カードの枚数が与えられ、どんな操作（置換・シャッフル）か定義されれば、元に戻るのに必要な手数も決定されるはずです。（つまりこの問題の一般化）
　質問者は、回答を判断し、ポイントを進呈し、回答を締め切らなければなりません。しかし、私は前に述べたように、数学の力からしてすでにその資格が無いようです。最初の問題についてはここで回答を締め切らせていただきます。一般化された問題については、できればどなたか数学の造詣が深い方に質問者になっていただけるとうれしいのですが。

回答No.1

taropoo

枚数が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)　
というところが、よく分かりません。たとえば、２＾３＝８ですが、
１２３４５６７８　→　１５２６３７４８　で、５番目の５はシャッフルによって２番目の位置にきています。
　ｆ３（５）＝　２　というわけですが、上の式では　５＞３　ですから
２（５－３）＝　４　となりそうなんですが。
私の理解が間違っているとは思いますが、よろしくお願いします。