この記事は、facebookのノートという機能を使って作成した記事の転載です。
モチベーション
2015年11月末に行われた京都大学特色入試では、一風変わった問題が出題されました。それを検討し、出題者の意図を考察したいと思います。まず、問題を示し、僕の考える模範解答を示したのち、ちょっと掘り下げます。
ちなみに、僕は数学者じゃないし、数学の専門教育を受けたこともありません。でも、試験問題を作る機会もあるので、作問者の視点というのがあって、そういう視点で見ると興味深いのです。
問題
n枚のコインを用いて一人で以下のゲームを行う。
・まず、ゲームの初期状態として、n枚のコインを円周上に等間隔に並べる。各コインは表または裏である。
・以下の操作を何回か繰り返す。
操作…並べたコインから連続するk枚を選び、選んだコインを全てひっくり返す。
・この操作を何回か行った結果、すべてのコインを表にすることができれば、ゲームは終了する。
初期配置の図
(1)n=7、k=3とする。初期状態が図1のとき、このゲームを終了させることができることを示せ。また、すべてのコインを表にするまでに必要な操作の最小回数を求めよ。
(2)n=6、k=3とする。初期状態が図2のとき、このゲームを終了させることができないことを示せ。
(3)どのような初期状態であっても必ずこのゲームを狩猟させることができるための、n、kに関する必要十分条件を求めよ。
答案概要
まずは、答案を作ろう。僕が予想する模範解答の概要は以下のようなものだ。
m番目のコインからk枚のコインを裏返す操作は、(可換)かつ(相殺)であるので、組み合わせで実現できる「簡約」な操作を考えることができる。簡約操作の総数はコインの状態の総数と一致するので、簡約操作に重複がない場合には、操作と状態が1対1写像になる。それは、任意の1枚のコインを裏返す操作が存在し、パズルが可解であることと同値である。
答案
定義 特にことわりのない限り、mを1~nまでの任意の整数とする。また、答案中に使われる文字変数はすべて整数である。
定義 m番目のコインからk枚のコインを裏返す操作をKmと書くことにする。また、Km=K(m)と書いてもよいとする。例えば、k=3のときは、3(1)のように書くことにする。
定理1 n枚のコインの表裏で決まる状態の種類は、2のn乗である。
証明 自明なので省略
定理2 (逆元・相殺)同じ操作を2回くらい返すと、元に戻る。すなわち、Km Km =φ。ただし、φは操作なしを意味する。
証明 自明なので省略
定理3 (可換)a, b=1 … n として、Ka Kb = Kb Kaである。
証明 ほとんど自明なんだけど、いちおうやっとく。
本系では、コインが円環状に配置されているので、a=1かつa<bとしても一般性を失わない。a+m≤bのとき、KaとKbはオーバーラップを持たないので、命題は自明。
a<b<a+kのとき、b番目から、a+k-1番目まで、オーバーラップがあることになるが、オーバーラップ域は、コインが2度反転して元に戻るだけ。これは順序が入れ替わっても同じ。なので、命題が成立する。
定理4 操作Kmを組み合わせて実現できるすべての操作の総数は2のn乗である。
証明 Kmの組み合わせは、Π(i=1…) K(1…nのいずれか)であらわされるが、定理3によって、操作順序を入れ替えることができるので、K1^Q1 K2^Q2 K3^Q3 …. Kn^Qn と書くことができる。ただし、Qiは正の整数。
さらに、定理2より、Qiは2の法とすることができるので、
Π(i=1…n) Ki^(Qi mod 2)=Π(i=1…n) Ki^(0 or 1)
つまり、n種類のKiのそれぞれについて、使うか使わないかという組み合わせ=可能な操作、となる。このようにKmの重複をなくした操作のことを簡約操作と呼ぶことにする。可能な簡約操作の組み合わせは、あきらかに、2のn乗である。
定理4’ 簡約操作は、特定のコインの状態に対応させることができる。
説明 Kmはコインの状態だけを変化させる操作である。したがって、任意の状態のコインに対し、あらゆるKmの操作とその組み合わせを適用することで、コインの状態が変化するものの、コイン以外の状態が変化することはない。例えば、すべて裏の状態を初期状態と仮定すれば、簡約操作のそれぞれは、何らかのコインの状態に対応付けることができる。数学用語で、「閉じている」という状態である。逆に、2つ以上の簡約操作が同じコインの状態に対応付けられるとき、重複していると言い、それらの簡約操作は等しいと言う。
定理5 n枚のコインの任意の1枚をひっくり返す操作が存在することの必要十分条件は、Kmの組み合わせで実現できる2^n個の簡約操作のすべてに重複がないことである。
証明 任意の一枚をひっくり返すことができれば、それを繰り返すことで、あらゆるコインの状態を実現できることは自明である。
定理4’により、コインの状態と簡約操作が対応し、定理1、定理4により、コインの状態と操作の総数が同じなので、重複があると、コインの状態数と操作の総数が対応しなくなり、すべてのコインの状態を作り出すことは不可能。任意の1枚のコインをひっくり返せるということと矛盾する。したがって、命題は正しい。
定理6 p、rを正の整数とし、n=pk+rのようにp、rを決める。このとき、Kmの組み合わせによって、~Rmを作ることができる。ただし、~は全コインの反転を表す。すなわち、~Rmはm番目からr枚のコインを残してすべて裏返す操作である。
証明 ほとんど自明。
~Rm=K(m+r) K(m+r+k) … K(m+r+(p-1)k)である。
定理7 kが奇数の時、全コインの反転~φ=Π(i=1…n) Kiである。
証明 ほとんど自明。
Π(i=1…n) Kiにおいて、すべてのコインは、k回の(裏返し)操作を受ける。kが奇数であれば、反転することになる。
定理7’ kが偶数の時、1(m)の操作をつくることができない。
証明 定理7と同様に、Π(i=1…n) Kiで、各コインはk回の操作を受ける。kは偶数であるので、Π(i=1…n) Ki=φとなる。簡約操作に重複があることになるので、定理4によって、任意の1枚のコインをひっくり返す操作1(m)は存在しない。
定理8 nとkが割り切れるとき、1(m)の操作をつくることができない。
証明 pを自然数として、n=pkとする。k=1のときはゲーム自体が成立しないので、除外できるため、kは2以上を考える。
2つの簡約操作Π(i=1, 1+k, … 1+(p-1)k)KiとΠ(i=2, 2+k, …, 2+(p-1)k) Kiを考える。これらの操作では、ともに、すべてコインが1回の反転操作を受ける。すなわち、
Π(i=1, 1+k, … 1+(p-1)k)Ki=Π(i=2, 2+k, …, (p-1)k) Ki=~φ
簡約操作に重複があるので、定理4によって、任意の1枚のコインをひっくり返す操作1(m)は存在しない。
定理9 定理6において、~φが存在するとき、Rm=~φ ~Rmである。
証明 自明
定理10 定理6において、k<rかつk=tr+sかつs=( k mod r)としたとき、Sm=Km R(m+s) R(m+s+r)…R(m+s+(t-1)r)である。
証明 ほとんど自明。
Kmで裏返したコインのうち、s枚を残してそれ以外のコインを1回あるいは複数回のR(m’)の操作によって再び裏返す。これにより、s枚のコインだけを裏返す操作Smを作ることができる。この操作を式で表すと、定理10となる。
(1) n=7、k=3
7=2×3+1なので、定理6において、p=2、r=1とすることができる。定理9によって、1m=~φ3(m+1)3(m+4)である。(ちなみに、1mの簡約操作は5回の操作で構成されるので、この表示の方がわかりやすいし、あとの計算が楽になる。)
コインの表を○、裏を●で表わし、コインの配置を○●○●●○●とする。左から、1…7の番号を割り当てる。裏返すコインは、2番4番5番7番の4枚になるので、1(2) 1(4) 1(5) 1(7)の操作を行えばよい。
1(2) 1(4) 1(5) 1(7)=(~φ)^4 3(3) 3(6) 3(5) 3(8-7) 3(6) 3(9-7) 3(8-7) 3(11-7) = 3(3)
3(6) 3(5)
3(1) 3(6) 3(2)
3(1) 3(4) = 3(2) 3(3) 3(4) 3(5)
この操作は簡約である。定理5より、任意の1枚をひっくり返す操作が存在するときには、簡約操作とコインの状態が1対1に対応する。したがって、この4回の操作が最小回数である。
補足 1mの操作があるときには、簡約操作に重複がないので、この簡約操作以外に図1の状態を全て表にする簡約操作は存在しない。とまで言及するのは蛇足か?あるいは、それを言わないとこの操作が最小手順であることを示したことにはならないか?
(2) n=6、k=3
前問と同様に、コインの配置を○●○○●●とし、左から1…6の番号を割り当てる。
3(4) 3(2)の操作を行うと、
○●○○●● 3(4) 3(2) =○●○●○○ 3(2) =○○●○○○
3番のコインだけ、裏となり、すべてを表にするには、1(3)の操作が必要になる。
n=6がk=3の場合、nがkで割り切れるので、定理8より、任意の1枚を裏返す操作は存在しない。したがって、1(3)の操作を作ることができない。ゆえに、解はない。
(3) パズルに解が存在する条件
任意の1枚をひっくり返せる場合、すなわち、1mが存在するには、パズルに必ず解があるのは自明である。逆に、任意の1枚だけをひっくり返した状態からスタートした場合、必ず1mが必要になるので、1mがない場合には、解けない場合が生じる。以上より、パズルに解が存在する必要十分条件は、1mの操作が存在することと結論できる。
定理10は、sをrに読み替えて、繰り返し適用することができる。定理6において、0≦r<nとすると、rはnをkで割った時の余りになる。すると定理6⇒定理10はnとkを対象にしたユークリッドの互除法になっていることがわかる。ユークリッドの互除法のあまりが最終的に1になれば、定理9によって、1mを作ることができるのは自明である。ユークリッドの互除法で、あまり1になるのは、nとkの最大公約数が1であるということである。普通には、nとkは既約と呼ばれる。
また、定理8より、kが偶数の時には1mを作ることができないので、これを除かなければならない。
まとめると、パズルに解が存在する必要十分条件は、kが奇数かつnとkが既約あること、である。
Discussion
この問題は明らかに、数学者としての「センス」を試すために作られている。高校までの数学は計算に大きなウェイトがあり、計算の手法を熟知し、自由に組み合わせる能力が高いほど、有利になっている。斯く言う僕も、ごく最近まで、数学=計算と思っていた。その意味では、数学というより算数と呼ぶことを好んでいた。その最近、ある本を読んで、現代数学というのは、数字を取り扱うことが目的じゃなくて、様々な事象に数学的構造を見出し、その構造を明らかにすることが本来の目的で、数というのはいろんな数学的構造のモデルを作り出すためのツールなんだ、ということを学んだ。それはまさしく、算数と数学の違いだ。大学では、本当の意味での数学をやっていかないといけないわけで、その素養を見たいというのはよく理解できる。ちなみに、そういうことをちゃんと説明してもらえなかったので、僕は学生の時に数学を完全に放棄した。
数学に対する一般の認識を受けて、大学入試では、計算の組み合わせに長けた人=数学に向いている人となっており、本当の意味での数学者の卵を選抜する仕組みになっていない、というのが大学側のジレンマとしてあったのだろう。その思いが、この問題から感じ取れる。Webで見ると、7x7や6x6の行列をつかった力技の解法が示されているが、いくらmod 2の系であっても、そんなに高次の逆行列を手計算で求めるのは大変だし、高校では高次の行列を扱わない。というか、最近は行列をやらない。行列を用いた解法は将来の受験生に対する誤ったメッセージになってしまうので、出題者側は避けるはずだ。代数的方法でパズルを解くと、このパズル自体の代数的構造をスルーしちゃうので、数学にならない。だから、出題者は、僕の答案のようなアプローチを期待してたと思う。
このコインのパズルは、典型的な群になっている。単位元φが存在し、逆元は同形で、可換で、というちょっと特殊だけど、立派な数体系(群)だ。その数体系を探り、性質を明らかにし、境界を見極めるという、数学の本来のありかたを比較的短い時間で達成できるように練られている。n=7のつぎにn=6を持ってきて系を単純化させて、解なしを導かせるのは、かなりのヒントになっている。これがn=5からn=6だと、ダメなのだ。このコインのパズルに数学的構造が存在することが、n=7によってピンとくるようになっている。というか、n=7をパズルとして解こうとするとちょっと難しい。n=7だと、必勝法を見つけなくてはならないと感じる。n=7だと、必勝法は比較的容易に見つかる。それは、任意の1枚をひっくり返す操作である。でもそれを組み合わせても最適解にはならない。最適解にするにはどうしたらよいか?すると、コインを反転する操作の性質(可換・逆元)を見つける。その性質を使って、公理系を構築することで、解の最適化に到達する。
最適化された解が、最少手数なのかどうかを証明するためには、もうひと山超えないといけないが、自前の演算系を構築し、運用できるセンスがあれば、超えることができると踏んだのだろう。そこを超えれば、あっという間に最後まで到達する。僕は3分だった。ただ、細部を詰めるには、数時間かかった。制限時間内で完全な答案を作成するのは僕には無理だ。
さて、高校生がこの問題を解けるか?と考えたとき、ちょっと難しいように思う。この問題は典型的な有限群で、操作に制限があって、対称性があるときとないときを議論するように設定されている。専門レベルの数学を知らない状態でアドリブで解けるなら、Abel級の才能かもしれない。出題者は明らかにそれを狙っているが、それは虫が良すぎるかもしれない。
こうしたパズルに数学的構造を見出すのはよくあることだ。このコインの話を一般化するとルービックキューブに近いものを作ることができる。1面3x3のルービックキューブは制限のついた単一の操作と有限の状態数で構成されたパズルで、今回のコインパズルに通じる。ただ、ルービックキューブを見て、数学的構造を解析する高校生は多分いない。でも出題者はそういう感性を持った人を望んでいるのだろう。成功したのかどうか、気になる。
ちなみに、京大数学科では、大学院は2種類あるそうだ。学者を目指すコースと、修士卒で民間に就職するコースだ。昨今、理系は修士卒じゃないとダメらしく、数学科も修士卒に対応しているらしい。従来、京大数学科の大学院は学者養成を目的としていて、ほとんど人を取らないことで有名だった。入試問題も強烈で、試験時間は4時間だったか5時間だったかで、とりあえずたっぷり与える。数問出題されるけど、1問完答できれば、文句なしで合格というものだ。ちょうど、今回の特色入試と似ている。というか、試験が数学オンリーな点も含めて、特色入試は数学科の学者コースの青田刈りなんだろう。それを思うと、今回の問題は高校生用にかなり調整されている。院試では、より抽象的で、解けるか解けないかギリギリな感じの問題が出題されると聞いている。もちろん、ノーヒントで。それを思うと、このコインの問題は簡単だと言える。だって、僕が数分で方針を立てられるんだから。
京大数学科の大学院の2つのコースは、数学を作る人と、使う人の差だと理解できる。このコインの問題は、数学を「作る能力」が試される。群論の知識なしでそれができるのなら、数学を作る能力が証明されることになる。ただ、数学マニアが受験することを考慮すると、もしかすると、僕のレベルの初等の群論は「知っている」可能性がある。「知っている」のと「使える」のにはかなりの差があるとはいえ、スレた数学マニアは排除したいというのが出題側の思いだろう。数学マニアが背伸びして及第というレベルは願い下げのはずだ。余裕ぶっこくくらいの人材が欲しいはず。ふれ込み通りなら、1題完答で合格なんで、このコインの問題だけでも解ければ合格になるはず。理学部は募集5名に対して、5名の合格者を出したので、1題完答では合格になっていない可能性が高い。スレた数学マニアが合格した可能性があって、残念なことにならないか心配だ。
追記:追跡調査のインタビュー記事で、部分点だけでの合格者が存在することが明らかになっている。というか、出題者が意図した完答はなかったのかもしれない。この試験後、難易度の高さが問題となり、次の年の試験では、かなり凡庸な問題が出題された。
さて、どのくらいの数学的厳密さを答案では要求するのだろう。僕は、自明と思えることにもかなり丁寧に説明を加えたけど、どのあたりで手を打つかは難しいところだ。現答案ですら、厳密さにおいては、いろいろ不足している。本当に完全な答案は、ほとんど論文になるだろう。だって、特定の数体系を解き明かすわけだから、それが新しければ、立派な論文だ。高校生たちにとっては、きっと「新しい」ので、論文作成と大差ないだろう。そういうレベルを入試で要求するとは思えない。採点基準は、アプローチのセンスの良さで決めるんだろうな。(3)は数学者としては重要なんだけど、それは厳密さが要求されるので、表現が難しい。僕は数学の専門教育を受けていないので、書き方がさっぱりわからない。(3)のゴールが見え見えなのもよくない。であれば、必勝法を少し一般化させて、n=7p+3、k=7の時に2mのあるなしを議論させるなんていうのも面白いかも。
僕の答案だと、最初に山ほど定理をつくって、設問は、ほぼ自明というパターンだけど、もし、作問者がこんな答案を候補に考えていたとするとちょっと違和感がある。それは、高校で一般的な数学の答案とは形式が大きく異なるからだ。それに、答案の一番のポイントは定理4と定理5で、ここでほとんどクライマックスだ。これを超えるとあとは作業でしかない。(1)はちょっと面白いけど、(2)は定理8で証明しちゃってます。(3)に到達しようとすると、定理8は必要なんだよね。そういうことを考えると、道具を全て作って本丸に攻め入るという典型的な数学の論文の体裁が効率的なわけです。それを高校生にやらせるのはちょっとどうなのかな、とも思う。
それよりも、定理5の山を越えてからが長いというのは問題だ。能力の測定は、定理5の時点で可能だ。それ以後の作業は試験時間の無駄にしかならない。能力を測定するという観点からは効率が悪い。
(3)の別解として、n、kが既約でない場合は、qn=pk(ただし、p、qは自然数で、p<n)となるp、qがあって、その場合にはk個の重複操作を簡単に見つけることができるので、1mが否定される、簡単に書くこともできる。ただし、nとkが既約の場合に1mができることを肯定しないので、別途1mの存在を証明しなくてはいけない。僕はユークリッドの互除法に類似の必勝法を提示したが、群表の性質を知っていれば、nとkが規約のときに、qn=pk+1となるp、qが見つかるのは自明で、それを使えば、必勝法をかなり簡単に作ることができる。僕は群論はちょっとしか知らない(ちゃんと勉強したことがない)ので、群表の性質をよく知らないし、その知識を高校生に求めるのはどうかと思う。
数学的構造に気づき、モデリングし、適切な介入(定理作成)を行う、というのは数学の作法だから、それができないとプロとしてやれませんよ、ということで良いと思う。僕の答案では、一見関係なさそうな手順を踏みながら、最後にバサバサ切り込んでゆく感じが数学チックで、僕は確かに楽しかった。
特に面白いのは、全反転操作の有無が重要だという点だ。そして、kが奇数の場合に作った全反転操作が、kが偶数の場合には全反転ではなく、無操作と重複するという点で、とっても面白い。それだけを見ると無味乾燥だが、1対1写像の場合には、1m操作の否定に結びつくというのが意外だ。多分、そういうのに、面白さを感じない人は、数学をやっちゃダメなんだと思うな。
僕は数学のプロパーではないので、もっと素晴らしい解法がある可能性を否定できない。しかしながら、(1)の計算はとても気持ちが良いもので、捨てがたい。いくつか思いついたとしても、この計算を答案に書かないという選択肢はないだろう。
設問を見ると、部分点を稼げる形になっている。すなわち、(1)は純粋なパズルなので、正解の4手順を見つけられるかもしれない。ただ、それが最小手順かどうかを示すことはできない。それに部分点を与えるのか?
(2)はコインの表裏の数の差の偶奇性からも証明できる。でもそれは発展性がない。部分点を与えても良いかもしれないが、それは計測したい能力とはほとんど無関係だ。特色入試は部分点で合否判定するような入試ではなかったはず。
(3)は必要十分条件を示すという点でちょっと難易度が高い。僕は1mの存在が必要十分条件で、それは簡約操作に重複がないことと同値だということをあらかじめ示したので、比較的簡単に証明できているけど、必要条件と十分条件を別々に示すのは、ちょっと難しい。結局、僕はそれが難しいと踏んで、たくさんの補題と代数的構造を調べることにした。(1)と(2)は捨てて、(3)だけを証明し、そのついでに(1)と(2)を解答するという形になっているのは、結構回り道した結果だ。そういう回り道できる能力を試すのなら良いが、時間の限られた試験という形式で、そのような判断を迫るのは理不尽だし、それを短時間で判断する能力は、数学的能力とはあんまり関係がない。
また、答案が長くなりすぎるのも問題だ。僕は「解けた」と確信するまでには数分だったけど、細部を詰めた答案作成には数時間かかった。問題の構造からして、定理5までできたら、ほぼ終わりだ。しかも、定理5まではほとんど自明。定理6は自明ではないけど、そこから先は作業でしかない。でもそこから詰めるのが大変だ。完全な答案を1時間程度で作成する能力は、数学的能力とは別物だ。特に、証明等の記述能力は大学生になってから磨けばよいものだと思う。入試の時点でそれを測る形式になっているのは良くない。何とか数学的な発想力だけを測定するうまい方法はないものか。