シャッフル　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　トランプのカードをマジシャンはきれいにシャッフルする。素人だとなかなか上手くいかな
い。世の中には、「自動トランプカードシャッフル機」なるものがあるそうだが、ここは、マジ
シャンになったつもりで、手作業による「シャッフル」の定義をしておこう。

　一口にシャッフルと言っても、いろいろ種類があるようだ。

　トランプのカードを片手に持って、山の下から数枚ずつ山の上に移動させることを繰り返
す方法（ヒンズーシャッフル）やトランプのカードを半分ずつ持って、カードが交互になるよ
うに重ねていく方法（リフルシャッフル）などが一般に知られている。

　このページでは、マジシャンがよくやるリフルシャッフルを話題にしたいと思う。

　いま、カードが ２ｎ 枚　　ａ₁、ａ₂、・・・、ａ_ｎ、ｂ₁、ｂ₂、・・・、ｂ_ｎ

あるとき、その順序を並べ替えて、

　　　　　　　　　　　　　　　 ｂ₁、ａ₁、ｂ₂、ａ₂、・・・・・・・・、ｂ_ｎ、ａ_ｎ

となるとき、
　　　　　　　　　２ｎ 枚のカードが「シャッフル」された

ということにする。
　　　　　　

例　２枚のカードについては、（１、２）→（２、１）→（１、２）　と２回シャッフルすると元に戻る。

例　４枚のカードについては、
　　　（１、２、３、４）→（３、１、４、２）→（４、３、２、１）→（２，４、１、３）→（１、２、３、４）
　　と４回シャッフルすると元に戻る。

例　８枚のカードについては、
　　　（１、２、３、４、５、６、７、８）→（５，１、６、２、７、３、８、４）→（７、５、３、１、８、６、４、２）
　→（８、７、６、５、４、３、２、１）→（４、８、３、７、２、６、１、５）→（２、４、６、８、１、３、５、７）
　→（１、２、３、４、５、６、７、８）　と６回シャッフルすると元に戻る。

　リフルシャッフルは、ヒンズーシャッフルに比べてカードに偏りがない切り方という印象があ
るが、リフルシャッフルを何回か繰り返すと元に戻ってしまう性質があるとは驚きですね！

　この「リフルシャッフルの性質」を題材にした問題が、平成１４年度の東京大学前期（理系）
入試で出題された。誘導の小問もあるが、ズバリ次の問いかけが眼目だろう。

　２^ｎ 枚のカードを、２ｎ 回シャッフルすると、元に戻ることを示せ。

　　　（一般の自然数 ２ｎ についてのシャッフル回数は、別表を参照）

　この事実が成り立ちそうなことは、上記の例からも明らかだろう。問題は、如何にして示す
かである。

　　２ｎ 枚のカードを、　１、２、・・・、ｎ、ｎ＋１、ｎ＋２、・・・、２ｎ　と順序をつけて並べ、この
数列をシャッフルしてできる数列で、数 ｋ が現れる位置を、Ｆ（ｋ） で表すことにする。

　このことは、前から数えて ｋ 番目の数は、シャッフル後、前から数えて、Ｆ（ｋ） 番目の位置
に現れるということである。

　シャッフルの定義から、

Ｆ（１）＝２、Ｆ（２）＝４、・・・、Ｆ（ｎ）＝２ｎ、Ｆ（ｎ＋１）＝１、Ｆ（ｎ＋２）＝３、・・・、Ｆ（２ｎ）＝２ｎ−１

なので、Ｆ（ｋ） のグラフを書けば、下図のようになる。

　　　

　この関数 Ｆ（ｋ） を何回か（ｍ回としよう！）合成して、　Ｆ^ｍ（ｋ）＝ｋ　となることを示せばよ
い。ただ、Ｆ（ｋ） のグラフを何となく眺めていても解決の糸口はつかめない。

　Ｆ（ｋ） のグラフは何となく扱いにくそうな雰囲気があるが、実は、ｍｏｄ （２^ｎ＋１）で考える
と、
　　　　　　　Ｆ（ｋ）≡２ｋ　（ ｍｏｄ （２^ｎ＋１） ）

という単純な構造になっていることが分かる。（→参考：合同式）

　このとき、　　Ｆ^ｍ（ｋ）≡２^ｍ・ｋ　（ ｍｏｄ （２^ｎ＋１） ）　である。

　ここで、　ｍ＝２ｎ　とすると、　２^ｍ−１＝（２^ｎ−１）（２^ｎ＋１）　より、

　２^ｍ−１≡０　（ ｍｏｄ （２^ｎ＋１） ）　すなわち、　２^ｍ≡１　（ ｍｏｄ （２^ｎ＋１） ）である。

　したがって、　ｍｏｄ （２^ｎ＋１）　において、　　Ｆ^ｍ（ｋ）≡２^ｍ・ｋ≡ｋ

　　　よって、　Ｆ^ｍ（ｋ）＝ｋ　となる。

　以上から、　２^ｎ 枚のカードを、２ｎ 回シャッフルすると、必ず元に戻る。


（コメント）　リフルシャッフルは、一見複雑そうな構造と思いきや、実は単なる「２倍」の構造
　　　　　　ということで、そんなに複雑なシャッフルは出来ないということなのだろう。それに
　　　　　　しても、この東京大学の問題を作問された先生の趣味の広さにはただ脱帽する
　　　　　　のみである。

（追記）　平成１９年７月２２日付け

　このシャッフルを入試問題にしたところが他にもあった。

＜２００７年度　聖心女子学院中等科　入試問題＞

　１から１０までの数字がひとつずつ書かれたカードが、はじめ図�Tのように一列に並べら
れていました。図�Tのカードの左側５枚と右側の５枚を交互に並べ、図�Uのように並べか
えました。

　　　　　図�T　　１　　２　　３　　４　　５　　６　　７　　８　　９　　１０

　　　　　図�U　　１　　６　　２　　７　　３　　８　　４　　９　　５　　１０

　１と１０の位置は変わりませんが、２から９までのカードはすべて位置が変わっています。
同じ並べかえをくり返し行うとき、次の問いに答えなさい。

　（１）　図�Uから、もう１回並べかえを行ったとき、はじめと同じ位置に戻るカードがあれば、
　　　その数字をすべて答えなさい。（１と１０は除きます。）

　（２）　すべてのカードが図�Tの並び方にはじめて戻るのは、この並びかえを何回行った
　　　ときですか。図�Tからの回数を答えなさい。

　（３）　図�Tから１００回並びかえたとき、１の右どなりにあるカードの数字はいくつですか。

　１と１０の位置は変わらないので、結局は、「２、３、４、５、６、７、８、９」のリフルシャッフル
の問題である。

　東京大学入試問題の公式を用いれば、２³ 枚なので、２×３＝６ 回シャッフルすると必ず
元に戻る。

　しかし、受験生は小学生なので、そのような解答は違反でしょうね？

　図�Tから図�Uの並べかえを精査すると、次のような巡回置換の積で表されることに気が
つく。
　　　　　　　　（ ２　３　５　９　８　６ ）（ ４　７ ）

（ ４　７ ）は互換なので、（ ４　７ ）（ ４　７ ）は恒等置換となる。

　このことから、（１）の解答は、「　４　と　７　」となる。

また、巡回置換 （ ２　３　５　９　８　６ ）は、　（ ２　３　５　９　８　６ ）⁶　が恒等置換となる。

よって、　（２）の解答は、「　６回　」となる。

（３）は、（２）を用いて解決される。　１００÷６＝１６・・・４　なので、

（ ２　３　５　９　８　６ ）¹⁰⁰（ ４　７ ）¹⁰⁰＝（ ２　３　５　９　８　６ ）⁴＝（ ２　８　５ ）（ ３　６　９ ）

すなわち、図�Tから、１００回の操作で図�Vとなる。

　　　　　図�V　　１　　５　　９　　４　　８　　３　　７　　２　　６　　１０

以上から、（３）の解答は、「　５　」となる。

（コメント）　小学生に置換の知識を期待することはできないが、置換を用いなくても紙と鉛
　　　　　　筆があれば解答を導くことが出来るだろう。それにしても、いい問題だ！

（追記）　平成２０年１１月３日付け

　当ＨＰの掲示板「出会いの泉」に、ＧＡＩ さんがこのシャッフルの話題に興味を持たれ、次
のような表を完成された。掲示板は時と共に消え去る運命なので、ＧＡＩ さんの結果をこの
ページに備忘録として残したいと思う。

　ＧＡＩ さんの結果から、公式の誤りに気づき、本文を修正させていただきました。上記は
修正済みです。ＧＡＩさんに感謝いたします。

　この表について、当ＨＰがいつもお世話になっているらすかるさんがプログラムを組まれ
て検証された。らすかるさんのご好意で、そのプログラムを公開されたので下記に記して
おきたい。

　※　見た目を良くするためにタブを全角スペースに置き換えているので、コンパイルする
　　　場合はタブかスペースに置換してほしいとのこと。

#include <stdio.h>
#include <string.h>

int buf[1000], bufw[1000];
int n;

void shuffle(void)
{
　int i;

　memcpy(bufw, buf, sizeof(buf[0]) * n);
　for(i = 0; i < n; ++i)
　　buf[i] = bufw[i / 2 + (i + 1) % 2 * n / 2];
}

int main(void)
{
　int i, c, cc;

　for(n = 2; n <= 1000; n += 2){
　　for(i = 0; i < n; ++i)
　　　buf[i] = i;
　　cc = c = 0;
　　do{
　　　++c;
　　　shuffle();
　　　for(i = 0; i < n; ++i)
　　　　if(buf[i] != n - 1 - i)
　　　　　break;
　　　if(i >= n && cc == 0)
　　　　cc = c;
　　　for(i = 0; i < n; ++i)
　　　　if(buf[i] != i)
　　　　　break;
　　}while(i < n);
　　printf("%3d %3d %3d\n", n, c, cc);
　}
　return 0;
}

（コメント）　プログラムには不慣れなもので．．．でも、見る人が見たら理解できるのでしょう！
　　　　　　らすかるさんに感謝いたします。