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

質問

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

回答No.12

neo_otacky · ベストアンサー

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

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

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

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

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

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

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

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

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

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

お礼

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

回答No.11

nagata

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

回答No.10

neo_otacky

一番上と一番下の位置が変わらないシャッフルですよね？
ワープロするのが大変なので、結論だけ書きます。

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

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

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

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

お礼

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

回答No.8

motsuan

シャフルを行列 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が偶数の場合の最後の１枚は順番が入れ替わらないことを反映しています）、
本質的には奇数の場合を考えればよいと思います。
いまのところ私には規則性が見出せません。

お礼

アドバイスしていただき、大変ありがとうございます。
　むかし勉強したようなことがたくさん書いてあって、冷や汗をかいています。皆さんにお願いするだけでなく、自分も復習くらいはしなければ・・・。
　私、今日から出張でヤマに入りますので、ネットからはずれます。きちんとレスができなくなりますが皆さまよろしくお願いします。

回答No.7

nagata

>有限回のシャッフルで、有限枚数のトランプが元に戻りそうなのは何となく分かります。が、初歩的な質問で恐縮ですが、「無限ループ」（元の状態には戻らず、いくつかの状態を千
>日手してしまう）には入りこまないのですか。これも群では常識でしょうか。

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

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

お礼

回答（解答）ありがとうございます。
　この点については、すっきりわかりました。
　本当にありがとうございました。

回答No.6

taropoo

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

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

補足

いえいえ。こちらこそ早速のレス、大変恐縮しています。
　この問題は本当に２０年以上考え続けている問題で（一部ウソ。１年間に数時間しか考えません）、このまま分からずに棺おけに入るのかなあ、と思っていた問題です。「教えて！ｇｏｏ」の皆様が頼りです。どうかよろしくお願いします。

回答No.5

abt-594

補足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さんのシャッフルとは逆の操作なので
下の例のＢの順位の経路も逆になってしまっています。

補足

何度もご丁寧に回答していただきありがとうございます。

　題意に合うようにabt-594さんのご回答を書き換えると、

　ｂ番目のカードがｂ’番目に行くとき、その関係は、カードの総数を２ｎとして、
（１）　ｂ＞ｎのとき、　ｂ’＝２（ｂ－ｎ）
（２）　ｂ＝＜ｎのとき、　ｂ’＝２ｎ－１
　ここで　あらたに　ｂ＝ｂ’として、コンピュータにシコシコ計算させれば、ｂ番目のカードが再びｂ番目に戻る手数がわかる、というわけですね。（合ってますか？）

　ここで、abt-594さんは各順番のカードの各手数を調べて、その最小公倍数が求める手数（題意ではシャッフル数）であろうとしていますが、紙と鉛筆で何回か実験（？）したところでは、どうやらｂ番目のカードがまたｂ番目に戻るときは、他のカードもそれぞれ元の位置に戻っており、「最小公倍数」はまさに各カードのその数になっているようです。（最小公倍数を考える必要がない）
　とすれば、例のアルゴリズムで計算した手数は、一応　２ｎ枚のカードが元に戻るシャッフル数を教えてはくれますが、本質的に、実際のカードを手で、あるいは紙と鉛筆でやってみたことを、計算機にさせているのと同じで、根本的なエレガントな解答ではないような気がします。（生意気なことを言って大変もうしわけありません）
　どうかよろしくお願いします。

回答No.4

abt-594

補足です

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

回答No.3

abt-594

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

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

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

(2)
b= b' とする

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

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

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

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

回答No.2

shushou

中高校生向けではありませんが。
これは置換という群に関する問題だと思います。
２ｎ枚のトランプの最初の状態を上から順に
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に置き換える、
という置換が生成する部分群の要素の個数をしらべればいいのでしょうが・・・。

補足

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