皆さんこんにちは。東大セミナーの北川です。夏が近づいてきた…‥というか、もうすっかり夏気分です。
ところで、夏をテーマにしたものというのは非常に多いですね。TUBEの『あー夏休み』やゆずの『夏色』なんかを聞くと、「今年も夏が来たなあ」という気持ちになります。
さて、今回も大学入試の問題を１つ取り上げ、その魅力や、この１問を通して受験生に身に着けてほしい力を解説して参ります。暑い夏に負けない面白問題を紹介できればと思います。どうぞ、最後までよろしくお願いします。
※この記事シリーズでは、数学の問題を取り上げることを通して、その問題の面白さや、すさまじさなどを一般の方にも伝わりやすく表現することに重きを置いています。
そのため、少々説明がくどくなったり、逆に必要ない部分は適宜厳密な議論を省略したりしています。ご了承いただけますと幸いです。
目次
今回扱うのはやや難しい数学の問題です。ですから、もしかしたら最後まで読み切るのに時間が掛かる方もいらっしゃることと存じます。そこで、最初に各節のザックリとした難易度感を出しておくことにします。
第1,2節：高校数学に対する知識に自信がなくても読めます。
第3節：高校数学に対する知識に自信がなくても少し頑張ると読めます。
第4節以降：難しい。高校数学に対する知識にあまり自信がないと、1時間以上は理解に時間が掛かる可能性があります。
今回扱う問題は、2002年の東京大学からの出題です。まずは、問題の意味は分からなくてもいいですから、見てみることにしましょう。
\(N\)を正の整数とする。\(2N\)個の項からなる数列
{\(a_{1},a_{2},\dots,a_{N},b_{1},b_{2},\dots,b_{N}\)}
を
{\(b_{1},a_{1},b_{2},a_{2},\dots,b_{N},a_{N}\)}
という数列に並び替える操作を「シャッフル」と呼ぶことにする。
（中略）
また、数列 {\(1,2,\dots,2N\)}をシャッフルした時に得られる数列において、数\(k\)が現れる位置を\(f(k)\)で表す。
（中略）
(1)数列{\(1,2,3,4,5,6,7\)}を3回シャッフルしたときに得られる数列を求めよ。
(2)\(1\text{≦}k\text{≦}2N\)を満たす任意の整数\(k\)に対し、 \(f(k)-2k\)は \(2N+1\)で割り切れることを示せ。
(3)\(n\)を正の整数とし、 \(N=2^{n-1}\)のときを考える。数列{\(1,2,3,\dots,2N\)}を\(2n\)回シャッフルすると、{\(1,2,3,\dots,2N\)}にもどることを証明せよ。
問題が少し複雑ですね。中略とした部分も含め、説明します。
まず、偶数枚のトランプをシャッフルするのを考えてください。それも、よくやるヒンズーシャッフル[1]ではなく、マジシャンがよくやるリフルシャッフル[2]の方を想像してください。
このリフルシャッフルを「寸分の違いもなく半分の束に分け、1枚の狂いもなく交互に嚙合わせて行うこと」[3]が、この問題における「シャッフル」です。
より正確に手順を述べると、
①まず、偶数枚のカードで作られたカード束を、ちょうど真ん中で半分に分けます。
②上の束の1番下のカード→下の束の1番下のカード→上の束の下から2番目のカード→下の束の下から2番目のカード→……という順で交互にカードを組み合わせます。
という感じです。
それを踏まえたうえで、問題(1)をこのように読み替えてみましょう。
(1)1から8までの数字が書かれたカードを、1が一番下、8が一番上になるように数字順で並べて束にしたものを用意します。この束を3回シャッフルすると、カードの並びはどうなりますか？
どうでしょうか。比較的分かりやすいですよね。
なんなら、手近にあるトランプから８枚取り出して、実際にシャッフルしてみても良いかもしれません。きっと、イメージを持ちやすくなるでしょう。
ちなみに、実際にやれば分かることなのでこの問題については答えを述べてしまいましょう。３回シャッフルすると、１から８までの数字が最初と真逆の順番で並びます。つまり、束の上から順番に8,7,6,…,1と並んでいれば正しくシャッフルできています。
余談ですが、東大の問題と言えど、(1)はこういう風に「実験」をすればすんなり答えが分かってしまう問題というのもあります。「わー問題文長くてめんどい！」と思っても、その意味を噛み砕いてしまえば案外シンプル、ということが起こるのは面白いですね。
[1] カードを何枚か束の中から引き抜き、上に重ねる動作を繰り返す方法。
[2] カードの束を半分ずつに分け、テーブルの上で1枚ずつ交互に重ね合わせる方法。
[3] パーフェクトシャッフルというそうです。
続いて、(2)の問題です。これはすんなりとは意味を理解しにくいですから、是非具体例を通して問題の主張を掴んでみましょう。お手元にトランプがあれば、是非今から説明することを実際にやってみてください！
まず、Nという文字が混じっているのがちょっと分かりにくいですね。特にNは正の整数であるという縛りしかないですから、仮にN=5として実験をしてみましょう。
N=5のとき、カードの枚数は2N枚、つまり10枚です。1から10までの数字が書かれたカードが、1を一番下、10を一番上として数字順に積み上げられた束を考えましょう。
この束を一度だけシャッフルします。この時、カードの並び順はどうなっているでしょうか。
実際に見てみると、下から順にこのように並んでいるはずです。
\(6,1,7,2,8,3,9,4,10,5\)
さて、ここで「どのカードがどの位置にあるか」を見ます。
例えば、7のカードは下から3番目にあります。3のカードは下から6番目にあります。
ここで、ある計算をします。あるカードについて、「そのカードが下から何番目にあるか」の答えから、「そのカードに書かれている数字」を2倍した数字を引き算します。
7のカードについてなら、3-7×2=-11
3のカードについてなら、6-3×2=0 などですね。
さてさて、こうして各カードについてこの計算を実行してみてください。そしてその答えをじーっと眺めてみてください。参考までに、各カードの計算結果を一覧にして並べておきます。
| カードに書かれている数字 | シャッフルによって移動した位置 | 計算結果 |
| 1 | 2 | 2-1×2=0 |
| 2 | 4 | 4-2×2=0 |
| 3 | 6 | 6-3×2=0 |
| 4 | 8 | 8-4×2=0 |
| 5 | 10 | 10-5×2=0 |
| 6 | 1 | 1-6×2=-11 |
| 7 | 3 | 3-7×2=-11 |
| 8 | 5 | 5-8×2=-11 |
| 9 | 7 | 7-9×2=-11 |
| 10 | 9 | 9-10×2=-11 |
めちゃくちゃ特徴的じゃないでしょうか。
0か-11しか出てきませんね。問題文中では「2N+1で割り切れる」とありましたが、0も-11も、共に2N+1=11で割り切れる数値ですよね。
(2)の主張はつまり、Nが5ではなく、どんな値であったとしても、このように「そのカードが下から何番目にあるか」の答えから「そのカードに書かれている数字」の2倍を引くと、2N+1で割り切れるはずだ！ ということなのです。
参考までに、より原文に寄せた書き方をしてみます。
(2)\(1\)から\(2N\)までの数字が書かれたカードを、\(1\)が一番下、\(2N\)が一番上になるように数字順で並べて束にしたものを用意します。この束を\(1\)回だけシャッフルします。
このとき、どのカードがどの場所に移動するかに注目します。\(k\)という数字が書かれたカードが、シャッフルで移動する先を下から\(f(k)\)番目と書くことにします。
\(f(k)-2k\)の結果が、\(2N+1\)で割り切れることを示してください。
さて、問題の主張が分かったところで、この問題を解く方針を考えましょう。
N=5の時の表をもう一度眺めてみましょう。カードの数字が1～5の時は、計算結果が0になっていました。6～10の時は、-11になっていました。
同じことが、いつでも成り立つと予想できるはずです。
つまり、1～Nまでのカードは計算結果が0に、N+1～2Nの時は-(2N+1)になるはずだ！ ということです。
簡単なため、ここでは1～Nのカードについて、計算結果が0になることを証明します。これができれば、本質的にはN+1～2Nのときも証明できます[4]。
そのためにはまず、1～Nのカードが、「シャッフルによってどこに移動するのか」を考えなくてはいけません。シャッフルの手順の最初で、カード束を半分に分けるくだりがありました。
この時、1～Nのカードというのは、「下の束」を構成するカードです。下の束のカードは、シャッフルによってどこに行くのでしょうか。
シャッフルでカードをかみ合わせる順番は、上の束のカード→下の束のカード→上の束のカード→下の束のカード→…という順番でしたね。ということは、下の束のカードは新しい束の2番目、4番目、6番目、8番目、…という風になるはずです。
つまり、1のカードは2番目、2のカードは4番目、3のカードは6番目、…という風になります。この状況は、\(k\)と書かれたカードは\(2k\)番目に移動している、とも形容できます。
以上の説明をまとめましょう。
ここまでに定義した記号を使うと、今しがた説明したことは\(f(k)=2k\)と書けます。先に「\(k\)という数字が書かれたカードが、シャッフルで移動する先を下から\(f(k)\)番目と書くことにします」と述べたのを思い出してみてください。
この\(f(k)=2k\)を、この問題における主となっていた計算式である、\(f(k)-2k\)に代入してみましょう。すると
\(f(k)-2k=2k-2k=0\)
となりますから、確かに1～Nについては、計算の結果は必ず0になることの説明がついたことになります！
これで言いたかったことが示せました。N+1～2Nについても、似たように「これらのカードはどこへ行くのか」を上手く式で示すことができます。是非チャレンジしてみてください。
[4] この証明は読者への演習課題とします。
(3)の問題の主張も理解していきましょう。
この問題はさっきと違って、Nの値に細かい指定があります。具体的には\(N=2^{n-1}\)という値のようですね。要するに、1,2,4,8,16,32,…[5]のように、2を何回か掛け算した値（2の累乗）ということです。
具体的に、\(N=4=2^2\)の時で考えてみましょう。
すると、1～8までのカードを使用することになります。このカードをシャッフルするのですが、今回はこのカード束を連続で6回シャッフルしてみましょう。
さて、どうなるでしょうか。実際にやってみると、以下のようになるはずです。
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回のシャッフルでカードは最初と全く同じ並びになります。
不思議じゃないですか？
同じようにN=2の時に4回シャッフルすると、元の並びと同じになります。
N=16の時に10回シャッフルすると、元の並びと同じになります。
さて、これが分かったところで、この問題の主張を確認しましょう。
ズバリ、「 \(N=2^{n-1}\)という形で表されるようなNについて、1～2Nのカードを、1を一番下、2Nを一番上にして数字順に並べた束を用意し、これを2n回シャッフルすると、元の配列に戻るよ」というのが主張です。具体的な数字を使って言うのなら、2枚の束なら2回、4枚の束なら4回、8枚の束なら6回、16枚の束なら8回、32枚の束なら10回、……のシャッフルで元に戻るということです。
ホンマに？って思いませんか。しかし、どうやら実験できる範囲については正しそうなことを言っています。果たして、本当に、（Nが2の累乗であれば）どんな枚数でも正しいのでしょうか。
まあ、受験の問題として「示せ」と言われているのでそりゃ正しいのですが、それで終わったらつまらないですよね。勿論解説します。
ただ、少しこれまで使ったことを、複雑に組み合わせて説明することになります。(3)は、(2)までより圧倒的に難しい問題になっているからです。
それでも興味があるよ！ という方はついてきてくださると幸いです。
[5] 今回はn=1の時、Nは1を取るため1もこの数列の中に含んでいます。
最初に、\(f(k)\)について考察します。
まず、 \(k\)と書かれたカードは、最初は下から\(k\)番目にあります。これは最初の並び順を考えれば明らかでしょう。
この \(k\)と書かれたカードは、最初のシャッフルによって \(f(k)\)番目に移動するわけです。
では、最初の状態から、シャッフルを2回繰り返すと、カードはどこに移動しているのかを考えます。
今、最初の束を2回シャッフルした時の \(k\)と書かれたカードの位置を \(f^2(k)\)と書くことにしましょう。この時、(2)と同様のことを考えてみましょう。
(2)の問題で述べられていたことというのは、つまり「シャッフルした後の位置」から「最初のカードの位置[6]」の2倍を引いた結果が2N+1で割り切れる、ということでした。これは、すべて「カードの位置」だけに着目した結果と言えます。
つまり、2度目のシャッフルについても、「カードの位置」だけに着目して、似たような結果を得ることができるのではないでしょうか。
具体的には、「2度目に束をシャッフルした後のあるカードの位置」から「最初に束をシャッフルした後にあったそのカードの位置」の2倍を引いた結果も、また2N+1で割り切れるということです。式で書いてみると、\(f^2(k)-2f(k)\)が2N+1で割り切れる、と書けます。
同様にして、何度かシャッフルした後のカードの位置に対し、同じようなことが言えます。
先と同様に、最初の束をm回（mは正の整数）シャッフルした時の、kと書かれたカードの位置を\(f^m(k)\)と書くことにしましょう。すると、\(f^m(k)-2f^{m-1}(k)\)が2N+1で割り切れることが言えます。
即ち、「m度目に束をシャッフルした後のあるカードの位置」から「m-1度目に束をシャッフルした後のそのカードの位置」の2倍を引き算した結果は、2N+1で割り切れます。
この気付きこそ、この問題の突破口です。
さて、問題文では2n回のシャッフルの後、カードがどこにあるかが鍵でした。
\(f^{2n}(k)-2f^{2n-1}(k)\)の結果は2N+1で割り切れるはずでした。さて、\(f^{2n}(k)-2f^{2n-1}(k)\)が2N+1で割り切れる、ということは、以下のようにも表現できるのではないでしょうか。
「 \(f^{2n}(k)\)と\(2f^{2n-1}(k)\)は、2N+1で割った余りが等しい」と。
んん？ と思う方もおられると思います。この問題とは直接関係はありませんが、少し具体例を注釈[7]に出しておきますから、理解に困った方は少し読んでみてください。
これと同様にすると、例えば\(f^{2n-1}(k)-2f^{2n-2}(k)\)の結果も2N+1で割り切れるはずでしたから、「\(f^{2n-1}(k)\)と\(2f^{2n-2}(k)\)は、2N+1で割った余りが等しい」ということです。
さて、この2つの事実をじっと見比べてみましょう。
「 \(f^{2n}(k)\)と\(2f^{2n-1}(k)\)は、2N+1で割った余りが等しい」…①
「\(f^{2n-1}(k)\)と\(2f^{2n-2}(k)\)は、2N+1で割った余りが等しい」…②
形が非常に良く似ています。そして、下線を付した二カ所は、「2倍されているかどうか」を除くと同じ形をしています。
そこで、下の主張も「全体を2倍する」ことで、上の主張と全く同じ部分を作り出してやりましょう。こんな感じです。
「\(2f^{2n-1}(k)\)と \(4f^{2n-2}(k)\)は、2N+1で割った余りが等しい」…②’
は!?と思われた方は、先と同じく注釈[8]を参考にしてみてください。
ともあれ、
「 \(f^{2n}(k)\)と\(2f^{2n-1}(k)\)は、2N+1で割った余りが等しい」…①
「\(2f^{2n-1}(k)\)と\(4f^{2n-2}(k)\)は、2N+1で割った余りが等しい」…②’
という新しい2つの主張を眺めてみましょう。ここから、このような主張が導けます。
「 \(f^{2n}(k)\)と\(4f^{2n-2}(k)\)は、2N+1で割った余りが等しい」
これはaとbが等しい、bとcが等しい、よってaとcもまた等しい、という論理の流れです。そして、このように「片方の主張の必要な部分を2倍」し、「等しいもの同士を等しいと主張する」操作を繰り返すと、以下のように続いていくはずです。
「\(f^{2n}(k)\)と\(4f^{2n-2}(k)\)は、2N+1で割った余りが等しい」
「\(f^{2n}(k)\)と\(8f^{2n-3}(k)\)は、2N+1で割った余りが等しい」
「\(f^{2n}(k)\)と\(16f^{2n-4}(k)\)は、2N+1で割った余りが等しい」
…
「\(f^{2n}(k)\)と\(2^{2n}k\)は、2N+1で割った余りが等しい」
この、最後の主張が鍵です。なぜならば、この主張は、今回の主題である「2n回シャッフルした後のカードの位置」と「最初のカードの数字」について結びつけるものだからです。
[6] (2)の問題と若干表記が違いますが、最初のシャッフルでは、カードに書かれている数字＝最初のカードの位置となるから、こう書いても実質的に同じというわけです。
[7] 例えば、9は3で割り切れます。一方で、13-4=9です。ここで、13を3で割った余りは1、そして、4を3で割った余りもまた1です。
このように、「引き算の結果がある数aで割れる」なら「引き算する前の2つの数は、ある数aで割った際に余りが等しい」ということを、本文では主張しているのです。
[8] 先と同じく、具体例で考えてみましょう。9は3で割り切れます。13と4は、共に3で割った余りが1でした。13と4を、両方2倍してみると、26と8になりますよね。26を3で割った余りは2、8を3で割った余りも2です。
このように、「ある2つの数をある数aで割った余りが等しい」ときに、「その2つの数を同じだけ何倍かして、そのあとある数aで割った余りも等しい」ということです。
さて、ここからがクライマックスです。分かっている情報を整理します。
まず、今回はNの値が具体的に与えられていました。\(N=2^{n-1}\)です。ですから、\(2N+1=2^n+1\)という値が与えられています。
これを、先ほど得られた主張にはめ込んでみます。
「\(f^{2n}(k)\)と\(2^{2n}k\)は、\(2^n+1\)で割った余りが等しい」
さて、この式をどうにかしていきましょう。
まずは\(2^{2n}k\)から一部を取り出して、\(2^{2n}\)という数値に注目しましょう。この数を\(2^{n}+1\)で割った値というのは、実は比較的すぐに分かります。
\(2^{2n}\)というのは、2を2n回掛けたものです。つまり、「2をn回掛けたもの」を2回掛け算したものです。よって、以下のように式変形ができます。
\(2^{2n}=2×2×\dots×2\)
\(=(2×\dots×2)×(2×\dots×2)\)
\(=2^n×2^n=(2^n)^2\)
さらに、以下のように式変形を続けます。
\((2^{2n})^2\)
\(=(2^{2n})^2-1+1\)
\(=(2^{2n})^2-1^2+1\)
\(=(2^n-1)(2^n+1)+1\)
二乗引く二乗の形を無理やり作り出して、一部分をかなり強引に因数分解しました。
式変形の結果をまとめるとこうなります。
\(2^{2n}=(2^n-1)(2^n+1)+1\)
右辺に注目してください。\((2^n-1)(2^n+1)\)の部分は、当たり前ですが\((2^n+1)\)で割り切れます。つまり、\((2^n-1)(2^n+1)+1\)を\((2^n+1)\)で割った際に、余る部分は1だけです。
左辺と右辺は等しいですから、\(2^{2n}\)を\(2^n+1\)で割った余りもまた、1です。
それに\(k\)を掛け算した\(2^{2n}k\)という数を\(2^n+1\)で割った余りは、どうなるでしょうか？ 結論だけを述べてしまえば、\(k\)を\(2^n+1\)で割った余りと等しくなるのです[9]。
この考察から、以下の情報が手に入ります。
「\(2^{2n}k\)と\(k\)は、\(2^n+1\)で割った余りが等しい」
これと、先ほどの主張を並べてみましょう。
「\(f^{2n}(k)\)と\(2^{2n}k\)は、\(2^n+1\)で割った余りが等しい」
「\(2^{2n}k\)と\(k\)は、\(2^n+1\)で割った余りが等しい」
さて、同じように、この主張たちの必要な部分だけを1つにまとめてみましょう。
「\(f^{2n}(k)\)と\(k\)は、\(2^n+1\)で割った余りが等しい」…★
これが言えると、実は、この問題は既に解けているも同然です。以下の項で説明しましょう。
先の★をつけた主張ですが、日本語で書いてみると、このような感じです。
「2n回シャッフルした後のkと書かれたカードの位置」は「カードに書かれている数字k」と、 \(2^n+1\)で割った余りが等しい。
ところで、「2n回シャッフルした後のkと書かれたカードの位置」は、カードが2N枚、つまり\(2^n\)枚しかないわけですから、1から\(2^n\)までのどれかの数になります。
同じように、「カードに書かれている数字k」も、1から\(2^n\)までのどれかの数になります。
ところで、\(2^n+1\)で割った余りもまた、1から\(2^n\)までのどれかの数になります[10]。さらに都合のいいことに、1から\(2^n\)までの中に、\(2^n+1\)で割った余りが等しくなるような数というのはありません。
だから、余りが同じ、ということは、今回に限っては実質的に割る前の数値そのものが同じだ、と言ってしまえるのです。つまり、
「2n回シャッフルした後のkと書かれたカードの位置」は「カードに書かれている数字k」と、 \(2^n+1\)で割った余りが等しい。
という事実はそのまま
「2n回シャッフルした後のkと書かれたカードの位置」は「カードに書かれている数字k」と等しい。
と読み替えることができ、要するにkと書かれたカードは2n回のシャッフルを経て、元の位置に戻ってきているということになります。
これこそ今回示したかったことでした！
kや\(f^{2n}(k)\)の取れる範囲が限られているからこそ、余りで絞り込むことが、そのまま致命の一撃として使えてしまったというわけです！
[9] 納得できない場合は、先の注釈を参考に、自分で具体的な数を持ってきて試してみてください。3で割って1余る数は例えば4ですが、4に何かを掛け算して3で割った余りは、4を掛け算する前に3で割った余りと同じになっているはずです。
[10] 余りとは、「割れるだけ割って残った数」ですから、割り切れたときは0に、そうでないときは1から\(2^n\)までの数値を取ります。今回は元々kや\(f^{2n}(k)\)の値が1から\(2^n\)までしかとらないから、余りが0になることはありません。
書き始めてから終わるまで、気がつけば3日近くかかっていました。
それでも今回この問題を取り上げた理由は、これが実り多く、豊かな示唆をもたらす良問だからに他なりません。
実際、今回の問題に必要だったことを挙げてみましょう。
どれもこれも、難関大学の問題に太刀打ちするために必須の能力です。さらに、途中で無理やり因数分解をする必要があったり、（本来解答を書くために必要な）合同式の扱いに慣れる必要があったり、という点は、整数問題の王道を行くような出題だと言えるでしょう。
さらに、大学数学まで目を向ければ、この問題は群論の知識を使って見ることもできます。
特に(3)の問題に対しては（少し専門的な言葉を使うと）、集合 \(X=\{1,2,3,4,\dots,2^n\}\)に対して、\(2^n\)次の対称群\(S_{2n}\)の元\(\sigma=(2,4,6,8,\)…\(,2^n-2,2^n,1,3,\)…\(,2^n-3,2^n-1)\)
から生成される群[11] \(\langle\sigma\rangle\)を作用させているという見方ができます。こう考えると、例えば軌道分解を考えることで、カードの移動に規則性が分かりやすく見えますから、より深い考察が可能です（多分）。
一度解けた後も角度を変えて色々遊ぶことができる、という点においてはまさしくこれは面白い問題だと言えます。
皆さんもこの夏は是非、シャッフルに隠された意外な数学の秘密を楽しんでみてはいかがでしょう？
[11] (3)が解けている時点で \(\sigma^{2n}=e\)(\(e\)は\(S_{2n}\)の単位元)が言えますし、逆元の存在も確認できるので群になっています。
東大セミナーを知る
コース紹介
会社案内
Copyright ©金沢市・野々市市・白山市の学習塾 - 東大セミナー All Rights Reserved.
