パズルの国のアリス

モグラ大学の卒業試験

 最初の問題だが,学生たちはある程度自分の成績の予測はつくだろうから,個々に勝負しても,ある程度以上の勝率は上げられる。しかし,その勝率がたとえば1/2とすると,半数が落第という悲惨な結果になるので,ここは一蓮托生案でいくしかない。問題は,そのときに成績推測のうまい戦略があるかどうかだ。

 実は各学生がでたらめに推測するという戦略でも,正答者が有限匹にとどまる確率は0である。なぜなら,その場合の正答率は1/5であり,回答者が無限匹だから,正答者数の期待値も無限になるからだ。だが,これはあくまでも確率の話で,正答者が有限匹しかいないということが論理的にありえないということではない。だから,正解者が論理的に無限匹になる戦略があれば,それにこしたことはない。

 そのような戦略のためのヒントは,実は2016年12月号への解答(2017年1月号掲載)の中にある。n=5の場合の変更案2に対する戦略を応用すればよいのだ。具体的にはたとえば次のようにする。学生たちは,近くにいるもの同士で5匹ずつのグループを作る。そしてその中で各メンバーに1から5の番号を振る。さて,目が悪いといっても,自分の前後10匹くらいは見えるというのだから,自分を除くグループの全メンバーの成績は見えるはずだ。そこでその4匹の成績を足し,そこから自分の番号を引く。それにいくつ足せば5で割り切れるようになるかを考えて,それを自分の成績の推測値とするのだ。そうすると,先月号の答えと同様,あるグループに属する5匹の成績の総和をSとすると,そのグループの中では,Sn(mod 5)を満たす番号nを持つ学生だけが正しく成績を推測する。結局,5匹の各グループごとに正解者が1匹ずつ出て,全体ではグループは無限個あるのだから,正解者数は確実に無限になる。

 次の問題はいささか厄介だ。まず前提が変わり,モグラたちは自分の成績を除いて全員の成績を知っている。ただし今度は,無限匹が正答するだけでは駄目で,誤答を有限匹にとどめねばならない。いくつか簡単な場合を先に考えておこう。たとえば,有限匹の例外を除き全員が同じ成績だった場合,全学生にそのことはわかるから,全員が自分の成績もそれと同じだと推測するという戦略が取れる。その結果,間違える学生は有限匹に限られるので,この卒業試験に合格できる。さらに,学生に通し番号を付けておいたとき,このとき有限箇所を除いて成績が完全に周期的だったとしよう。たとえば,1000番より後では8匹ごとに1,2,2,3,3,4,4,5という成績が繰り返して現れていたとする。すると,途中から同じ成績が繰り返していることは全学生にわかるから,最初から全成績が同じパターンを繰り返すとして,自分の成績を推測すればよい。この場合も,間違えるのは周期が始まる前のせいぜい1000匹だから学生たちの勝利だ。

 実は,パターンの繰り返しがない場合も,学生たちの戦略は基本的には上と同じである。一般に学生たちの成績一覧を考え,それをsとしよう。学生たちには1から番号を振ってあるとすると,sは自然数の集合Nから{1,2,3,4,5}への関数と考えることができる。このコラムでも何度か取り上げたように成績一覧sは,色々とありうるが,そのバラエティの総数は非可算無限個だ。2つの成績一覧stが有限箇所しか違わない場合,stと書くことにする。ポイントは〜が数学で言う同値関係というものになることだ。つまり,次の3つの条件が成り立つ。

(1)ssである。
(2)stならばtsである。
(3)stかつtuならばsuである。

 初めの2つの条件は明らかだろうから,(3)について述べると,stmカ所で異なり,tunカ所で異なるならば,suの違いはせいぜいmnカ所にしかならないからだ。

 stならばstはいわば同じ家族のようなもので,これに従って,すべての成績一覧を分類することができる。sを1つの成績一覧とするとき,それと有限箇所しか違わない成績一覧の全体{tts}を[s]と書き,sの同値類と呼ぶ。すると,すべての成績一覧はどこかの[s]に納まり,他の[t]に二重に属することはない。さて,各同値類[s]が家族のようなものとすると,それぞれの代表(家長)を決めることができる。あとは簡単である。学生たちは,自分の成績がわからないので本当の成績一覧は完成できないが,他のすべての成績がわかるのだからそれがどの[s]に属するかは判定できる。それを代表するのがsだとすると,sの通りに自分の成績を推測すればよい。こうすれば推測を外す学生は有限匹だから,学生たちの勝利は確実である。

 当たり前のように書いたが,「各同値類[s]の代表(家長)を決めることができる」としたのが,実は選択公理にほかならない。この部分を読んで怪しいと思われた読者は,この戦略の問題点を正しく認識しておられる。先に述べたように,途中から同じパターンが繰り返すような成績一覧であれば,完全な繰り返しパターンを代表とすることに誰も異存はないだろう。しかし,どの成績一覧をとっても,それと有限箇所で異なっている成績一覧は可算無限個あるのだから,まったくパターンが見えない成績一覧の場合には,どれを代表にするかについて学生間で了解がなければ戦略は実行できない。まして同値類[s]自体の数は非可算無限個ある。つまり,可算無限個の要素からなる同値類の中から代表を選び出すということを,前もって非可算無限回にわたって繰り返したあとでないと実行できない戦略ということだ。

 もちろん,無限匹いる自分以外の成績を完全に把握できるような学生たちなのだから,そのくらいの選択を前もってやっておくことなど朝飯前だと言われれば,そんなものかと思って黙り込むしかない。というわけで,無条件の選択公理の使用に筆者は懐疑的だが,そのような数学者はむしろ少数派かもしれない。

 ところで,上記の戦略にあたって必要なのは,有限匹を除いて全学生の成績がわかることだけだから,自分より大きい番号の全学生の成績がわかるだけでも学生側が勝利できることを付記して,本稿を締めくくるとしよう。

問題はこちらです