シャッフル
トランプのカードをマジシャンはきれいにシャッフルする。素人だとなかなか上手くいかな
い。世の中には、「自動トランプカードシャッフル機」なるものがあるそうだが、ここは、マジ
シャンになったつもりで、手作業による「シャッフル」の定義をしておこう。
一口にシャッフルと言っても、いろいろ種類があるようだ。
トランプのカードを片手に持って、山の下から数枚ずつ山の上に移動させることを繰り返
す方法(ヒンズーシャッフル)やトランプのカードを半分ずつ持って、カードが交互になるよ
うに重ねていく方法(リフルシャッフル)などが一般に知られている。
このページでは、マジシャンがよくやるリフルシャッフルを話題にしたいと思う。
いま、カードが 2n 枚 a1、a2、・・・、an、b1、b2、・・・、bn
あるとき、その順序を並べ替えて、
b1、a1、b2、a2、・・・・・・・・、bn、an
となるとき、
2n 枚のカードが「シャッフル」された
ということにする。
例 2枚のカードについては、(1、2)→(2、1)→(1、2) と2回シャッフルすると元に戻る。
例 4枚のカードについては、
(1、2、3、4)→(3、1、4、2)→(4、3、2、1)→(2,4、1、3)→(1、2、3、4)
と4回シャッフルすると元に戻る。
例 8枚のカードについては、
(1、2、3、4、5、6、7、8)→(5,1、6、2、7、3、8、4)→(7、5、3、1、8、6、4、2)
→(8、7、6、5、4、3、2、1)→(4、8、3、7、2、6、1、5)→(2、4、6、8、1、3、5、7)
→(1、2、3、4、5、6、7、8) と6回シャッフルすると元に戻る。
リフルシャッフルは、ヒンズーシャッフルに比べてカードに偏りがない切り方という印象があ
るが、リフルシャッフルを何回か繰り返すと元に戻ってしまう性質があるとは驚きですね!
この「リフルシャッフルの性質」を題材にした問題が、平成14年度の東京大学前期(理系)
入試で出題された。誘導の小問もあるが、ズバリ次の問いかけが眼目だろう。
2n 枚のカードを、2n 回シャッフルすると、元に戻ることを示せ。
(一般の自然数 2n についてのシャッフル回数は、別表を参照)
この事実が成り立ちそうなことは、上記の例からも明らかだろう。問題は、如何にして示す
かである。
2n 枚のカードを、 1、2、・・・、n、n+1、n+2、・・・、2n と順序をつけて並べ、この
数列をシャッフルしてできる数列で、数 k が現れる位置を、F(k) で表すことにする。
このことは、前から数えて k 番目の数は、シャッフル後、前から数えて、F(k)
番目の位置
に現れるということである。
シャッフルの定義から、
F(1)=2、F(2)=4、・・・、F(n)=2n、F(n+1)=1、F(n+2)=3、・・・、F(2n)=2n−1
なので、F(k) のグラフを書けば、下図のようになる。
この関数 F(k) を何回か(m回としよう!)合成して、 Fm(k)=k となることを示せばよ
い。ただ、F(k) のグラフを何となく眺めていても解決の糸口はつかめない。
F(k) のグラフは何となく扱いにくそうな雰囲気があるが、実は、mod (2n+1)で考える
と、
F(k)≡2k ( mod (2n+1) )
という単純な構造になっていることが分かる。(→参考:合同式)
このとき、 Fm(k)≡2m・k ( mod (2n+1) ) である。
ここで、 m=2n とすると、 2m−1=(2n−1)(2n+1) より、
2m−1≡0 ( mod (2n+1) ) すなわち、 2m≡1 ( mod (2n+1) )である。
したがって、 mod (2n+1) において、 Fm(k)≡2m・k≡k
よって、 Fm(k)=k となる。
以上から、 2n 枚のカードを、2n 回シャッフルすると、必ず元に戻る。
(コメント) リフルシャッフルは、一見複雑そうな構造と思いきや、実は単なる「2倍」の構造
ということで、そんなに複雑なシャッフルは出来ないということなのだろう。それに
しても、この東京大学の問題を作問された先生の趣味の広さにはただ脱帽する
のみである。
(追記) 平成19年7月22日付け
このシャッフルを入試問題にしたところが他にもあった。
<2007年度 聖心女子学院中等科 入試問題>
1から10までの数字がひとつずつ書かれたカードが、はじめ図Tのように一列に並べら
れていました。図Tのカードの左側5枚と右側の5枚を交互に並べ、図Uのように並べか
えました。
図T 1 2 3 4 5 6 7 8 9 10
図U 1 6 2 7 3 8 4 9 5 10
1と10の位置は変わりませんが、2から9までのカードはすべて位置が変わっています。
同じ並べかえをくり返し行うとき、次の問いに答えなさい。
(1) 図Uから、もう1回並べかえを行ったとき、はじめと同じ位置に戻るカードがあれば、
その数字をすべて答えなさい。(1と10は除きます。)
(2) すべてのカードが図Tの並び方にはじめて戻るのは、この並びかえを何回行った
ときですか。図Tからの回数を答えなさい。
(3) 図Tから100回並びかえたとき、1の右どなりにあるカードの数字はいくつですか。
1と10の位置は変わらないので、結局は、「2、3、4、5、6、7、8、9」のリフルシャッフル
の問題である。
東京大学入試問題の公式を用いれば、23 枚なので、2×3=6 回シャッフルすると必ず
元に戻る。
しかし、受験生は小学生なので、そのような解答は違反でしょうね?
図Tから図Uの並べかえを精査すると、次のような巡回置換の積で表されることに気が
つく。
( 2 3 5 9 8 6 )( 4 7 )
( 4 7 )は互換なので、( 4 7 )( 4 7 )は恒等置換となる。
このことから、(1)の解答は、「 4 と 7 」となる。
また、巡回置換 ( 2 3 5 9 8 6 )は、 ( 2 3 5 9 8 6 )6 が恒等置換となる。
よって、 (2)の解答は、「 6回 」となる。
(3)は、(2)を用いて解決される。 100÷6=16・・・4 なので、
( 2 3 5 9 8 6 )100( 4 7 )100=( 2 3 5 9 8 6 )4=( 2 8 5 )( 3 6 9 )
すなわち、図Tから、100回の操作で図Vとなる。
図V 1 5 9 4 8 3 7 2 6 10
以上から、(3)の解答は、「 5 」となる。
(コメント) 小学生に置換の知識を期待することはできないが、置換を用いなくても紙と鉛
筆があれば解答を導くことが出来るだろう。それにしても、いい問題だ!
(追記) 平成20年11月3日付け
当HPの掲示板「出会いの泉」に、GAI さんがこのシャッフルの話題に興味を持たれ、次
のような表を完成された。掲示板は時と共に消え去る運命なので、GAI さんの結果をこの
ページに備忘録として残したいと思う。
GAI さんの結果から、公式の誤りに気づき、本文を修正させていただきました。上記は
修正済みです。GAIさんに感謝いたします。
枚数 | 同順復元回数 | 逆順復元回数 | 枚数 | 同順復元回数 | 逆順復元回数 | |
2 | 2 | 1 | 52 | 52 | 26 | |
4 | 4 | 2 | 54 | 20 | ||
6 | 3 | 56 | 18 | 9 | ||
8 | 6 | 3 | 58 | 58 | 29 | |
10 | 10 | 5 | 60 | 60 | 30 | |
12 | 12 | 6 | 62 | 6 | ||
14 | 4 | 64 | 12 | 6 | ||
16 | 8 | 4 | 66 | 66 | 33 | |
18 | 18 | 9 | 68 | 22 | ||
20 | 6 | 70 | 35 | |||
22 | 11 | 72 | 9 | |||
24 | 20 | 10 | 74 | 20 | ||
26 | 18 | 9 | 76 | 30 | ||
28 | 28 | 14 | 78 | 39 | ||
30 | 5 | 80 | 54 | 27 | ||
32 | 10 | 5 | 82 | 82 | 41 | |
34 | 12 | 84 | 8 | |||
36 | 36 | 18 | 86 | 28 | ||
38 | 12 | 88 | 11 | |||
40 | 20 | 10 | 90 | 12 | ||
42 | 14 | 7 | 92 | 10 | ||
44 | 12 | 94 | 36 | |||
46 | 23 | 96 | 48 | 24 | ||
48 | 21 | 98 | 30 | 15 | ||
50 | 8 | 100 | 100 | 50 |
この表について、当HPがいつもお世話になっているらすかるさんがプログラムを組まれ
て検証された。らすかるさんのご好意で、そのプログラムを公開されたので下記に記して
おきたい。
※ 見た目を良くするためにタブを全角スペースに置き換えているので、コンパイルする
場合はタブかスペースに置換してほしいとのこと。
#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;
}
(コメント) プログラムには不慣れなもので...でも、見る人が見たら理解できるのでしょう!
らすかるさんに感謝いたします。