最新閲覧日:

 この問題は私が高校生の時に「発見」したものですが、いまだに解けなくて困っています。どなたか数学に強い方解いて下さい。できれば、中・高校生にも分かる解法でお願いします。
○偶数(2n)枚のトランプがある。これを前半と後半の2つに分け、1枚ずつ互い違いになるように何回かシャッフルすると、最初にトランプのカードが並んでいた状態に戻るようである。 必ず戻るのか、証明せよ。 もしそうなら、トランプの枚数2nと、戻るのに要するシャッフルの回数mとの関係はどうなるか。
○少し説明します。
・トランプ6枚のとき
 ABCDEF>ADBECF>AEDCBF>ACEBDF>ABCDEF で、4回で元に戻ります。最初のカード(A)と最後のカード(この場合はF)はその位置が変わりません。2回シャッフルしたときにアンコの部分がちょうど逆転していて、4回で元に戻ることが予想できます。
・トランプ8枚のとき
 ABCDEFGH>AEBFCGDH>ACEGBDFH>ABCDEFGH で、3回で元に戻ります。回数は6枚のときより少なくなりました。
・トランプ10枚のとき
 ABCDEFGHIJ>AFBGCHDIEJ>AHFDBIGECJ>AIHGFEDCBJ>AEIDHCGBFJ>ACEGIBDFHJ>ABCDEFGHIJ  で、6回で元に戻ります。このときも、3回シャッフルしたときに中身の部分が逆転しています。
・いろいろやってみると、(1)おおよそ、枚数2nが増えるほど、元に戻るまでのシャッフルの回数mは増加する傾向がある。(2)しかし、2nが2の累乗(4,8,16・・・)のときには回数が減るようである。 ということは分かっているのですが・・・・。どなたかよろしくお願いします。

このQ&Aに関連する人気のQ&A

A 回答 (12件中11~12件)

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


これは置換という群に関する問題だと思います。
2n枚のトランプの最初の状態を上から順に
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枚を後半として
同じように何回かシャッフルすると元に戻ります。
さらにさらにすごいことに、どんなシャッフルの仕方でも
何回かやると元に戻るんです!
つまり、たとえば「後ろの2枚を1枚目と2枚目の間に入れる」
という変則的なシャッフルでも元に戻ります。
6枚でやってみましょう。
123456→156234→134562→162345→145623→123456
という風に。(7枚だと元に戻るのははっきり言って当たり前。)
以上のことは、全て置換群の考えで説明できます(多分)。

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

この回答への補足

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

補足日時:2001/07/29 09:08
    • good
    • 0

枚数が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) 
というところが、よく分かりません。たとえば、2^3=8ですが、
12345678 → 15263748 で、5番目の5はシャッフルによって2番目の位置にきています。
 f3(5)= 2 というわけですが、上の式では 5>3 ですから
2(5-3)= 4 となりそうなんですが。
私の理解が間違っているとは思いますが、よろしくお願いします。
       

補足日時:2001/07/29 08:59
    • good
    • 0

このQ&Aに関連する最新のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード


このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ