2017/10/03

【読書メモ】 パズルの国のアリス

パズルの国のアリス 坂井 公  日経サイエンス』
サブタイトルは、美しくも難解な数学パズルの物語、とあり、物語とはいっても数多くの単問パズルが次々と呈される編成になっている。
数学の難問が本当に美しいかどうかはさておき、僕なりに本書を手に取った理由は、データエラー検出や修復に用いる符号論理(ハミング符号列)がいくつかの解答案に引用されており、また別問にては「暗号における論理演算」の基本もカチッと引用されていて、インダストリアルな技術の源泉はやはり数学にあったのかと直観したため。

さてそれではと、本書にて続々と投げかけられる(超)難問に挑んでみれば、あらためて数学の複合的ないし多段的?な構成力に感嘆させられる、とともに、しばしば紹介されているいわば「エレガントな解法」に呆気にとられることも。
こうなってくると、たとえば僕が永年に亘り仇敵のごとく憎悪してきた整数論にせよ、ちょっとは自信があった確率変動にせよ、全体の多段的な構成にてはあくまでひとつの調整弁に如かず、と、しばしため息が漏れ出でてしまうほどである (だからといって僕自身が数学好きになったわけでもないし、こんごも好きにはなれそうもないのだが。)

そもそも、何を前提命題とし、いかなる解法を投入させ、どこまで至れば正解を成すのかというパズル化において、数学ほどに自在な思考体系は他にあるまい。
少女アリスが次から次へと難問のワンダーランドに迷い込んでゆくという本書ならではの演出にせよ、若さ、直観力、飛躍力への誘いの趣きか、かつ、絶妙の問題設定の数々はカードゲームなどのプログラム設計をも想起させてやまない。

さて、以下にいくつか引用する此度の読書メモにては、本書のパズル形式の性質上、とくに前提と解法と正解を切り分けずに、概括的に列記してみることとした。


第18話
真の金貨と偽の金貨が一定数在るとして、その真偽判定のために最も効率的な計算手順を問うもの。
…といえば極めて簡単そうだが、ここに「無効な計測結果が混入しているかもしれない」 との前提条件が付加されており、それでも真偽判定の計算手順は変わらないだろうか、と問いかける
本問への解答案として引用されているのが、無効レコードの検出に活用される「ハミング符号」である。
ハミング符号につき、(僕なりにはるか遠い記憶を手繰り寄せつつ)思いきり要約するに ─ 2進数ほか或る進数の或るビット長における演算結果が白か黒か、を判別するためではなく、「白でも黒でもない演算結果を検出し、だから件数勘定から排除も出来る」ための符号順列…じゃなかったかな。
そうであれば、ハミング符号は、「それら以外では存在しえない(起こり得ない)はず」の最小限の進数/ビット長の順列である。
本問は前段部にて、3進数4ビット長のハミング符号の順列が概念投入されており、また後段部にては2進数7ビット長のハミング符号順列が誘導されている。
さぁ、これらによって「無効なデータが黙殺される」としたら、金貨の真偽判定のための計算手順は変わってしまうか、それとも変わらないか?

=======================

第6話
こちらは、上にあげた第18話にて挿入されているハミング符号の順列を、ヨリ多段的に応用したもの。
7人が頭に戴く冠の色が、白か、赤か、これを2進数7ビットで表現できるというところまではすぐ思い当たるとしても、「どっちかわからない」とのオプションあり。
たとえ「わからない」が含まれていても、2進数7ビットのうちハミング符号は16列しか無いのだからこれを上手く活かせ、と誘う解答案は、かなり閃きの難度が高いのではなかろうか。
それどころか本問は、おのれの冠の色を当てるか外すか或いはわからないで通すかによって、ゲームの利得が変わってくる、との条件付きであり、ここまで込み入ってくると、解法を読みおおせてみても了解は難しいのではないか。

※ なお、ハミング符号、完全符号などなどエラー検出の数理論については、p.27の末尾にも概説の一端が有るが、総括的には行列とベクトルによる符号理論として体系化されているようである。
こういうのが好きな人は、どんどん深みにはまってゆけばよかろう、また、自分でなんらかの数理ゲームをデザインしてみようなどという変人にとっても、なかなか愉快なトリック源たりうるのではないかな。

=====================

第21話
0から15までのカードのどれか1枚を、16枚のコインの表裏の出方によって仲間が言い当てる、というトリックゲーム。
これもじつに誘導的な設問になっていて、16枚のコインのうち1枚を故意にひっくり返すと、それが仲間に対してのカードNo.の合図となっている、という。
いったいどんなトリックなのだろうか…ここで解答案として導入されているのが、いわゆる「排他的論理和」の演算である。
例えばだが、初めに裏になってしまったコインNo. と、当てるべきカードNo. と、この両者まじえた排他的論理和を2進数にて演算し、この演算結果「番目」のコインをあえてひっくり返す。
その上にて、仲間がこれらコインからあらためて排他的論理和を演算し、それから10進数に戻すと、その数が問題のカードNo.にぴたり一致する、というトリックだ。
本当にそうなるのだろうか、いや、おのれがコンピュータになったつもりで演算してみればよい。
とまれ、排他的論理和のコンセプトそのものではなく、これを千里眼のごときトリックに応用するという飛躍センスこそが、「超」難しい。
(こういうロジカルトリックこそが、ロープレやカードゲームにふんだんに仕込まれているのではないかしら、よくは知らないけれども。)

=====================

第13話
本問は題意そのものがちょっと捕捉しにくい。
或るアナログ円時計の長針(つまり「時針」)と短針(つまり「分針」)の長さがまったく同じである、として、このどちらの針も分刻みの目盛りまで正確に指す、とする。
この前提にて、「何時何分を指しているのか判別できない」タイミングは1日24時間のうちに何回起こるか?
…というのがおそらくは題意であろうが、残念なことに例示的な図案が呈されていないため、「何時何分か判別できない」とはいかなる状態であるのか、アナログ的にイメージし難い。
例えば、2時30分頃なのか、はたまた6時12分頃なのか、こういうのが時間判別できないタイミングの意ではないか、とも察せられるが。

それでも、とりあえず代数計算によって解法は確立されている。
或る t時 までの時針と分針の回転数をまず定義、かつ、別の s時 までの時針と分針の回転数も定義する。
時針と分針がともに分刻みの目盛りをピタリと指す、そのタイミングこそが、何時何分か判別出来ない時である、とすると、つまり時針と分針がともに整数であるタイミングだ、さぁその回数は0時~24時までの間に幾つ有るか?
─ なるほど、こうやって見れば実に簡単な代数によるとデジタルな解法である、が、本書では仰天するような別案も紹介されていて、それはなんと、分針の12倍の速度で回る「第三の針」を想定して、これが時針に重なるタイミングおよび分針に重なるタイミングを数え、その勘定数をもとに本設問の解法に向かう、というものである。
こういうのがデジタル思考の発展形であるのか、いや、もしかしたらアナログ的な大飛躍なのかもしれぬが。

======================

第4話
これは本書にても典型的な複合問題のひとつであろう。
トランプカードの神経衰弱ゲームで、2人が交互に自分の番に裏のカードを2枚ずつひっくり返し、もしその2枚の数が合致したらそのまま続けて次の2枚に挑む
…というルールであるが、これは細かく場合分けすればもうちょっと戦略的に込み入っていて、「おのれが既に表の数字を知っている」カード1枚を捲るか、「全く未知の新たな」1枚を捲ってみるか、これで戦略がまず変わる。
「全く未知のカードを1枚捲ってみた」場合に、続く2枚目のカードとしては既に確認済のものを捲るか、あるいは全く未知のものをランダムに選ぶか、このどちらかによっても「成功の期待値」が変わってくる。
もちろん、こうして挑んだ2枚目が当たりか外れかによっても、「更なる成功の期待値」は変わってくる。
では、この神経衰弱にて、出来るだけおのれに有利にゲームを運ぶためには、どういう戦略をとってゆけばよいか…?!

ちょっと考えるだけでも頭がどうにかなりそうな難題だ。
解法の道筋としては、裏返っているカードの残数(2の倍数として)と、既に一度は捲ってしまい表が分かっているカードの数をまず定義、この「両者の数値によって勝率全体が決まる」、としつつも、各局面ごとの成功の確率もまたこの両者の比によって別個に変わってくる、とする。
こうして、確率変動と期待値の項を複数足し合わせた(あるいはマイナスした)形の漸化式をつくり…

本問はとにかく多段的というべきで、付録的に提示されているカード枚数(残数)と期待値の実践的なマトリクスに、目が眩みそうである。
さはさりとて、これもまたカードゲームなどにおける実践的な数理アプリケーションたりえよう、そして本設問と解法はけして突飛な飛躍を課すものでもなかろう。

=====================

第34話
これは暗号演算の数理の一つで、いわゆる3パス・プロトコルの適用だ。
もう設問までいちいち引用するのも面倒になったので、3パス・プロトコルの数理手法について本書引用の箇所をさらりと紹介しおく。

或る平文を c とし、これを暗号化したものを、暗号文 d, e, ...  とする。
送信者Aの目的は、この平文c を暗号化して受信者Bに送ることであり、受信者Bの目的はそれを復号化して元の平文cを入手すること。
暗号化の鍵関数として、送信者Aは関数f逆関数f- 1  のみを知っており、一方で受信者Bは関数g と逆関数g- 1 のみを知っている。
さて、送信者A は、平文cを関数f暗号化し、d = f(c) として受信者Bに送る。
B は、この暗号文dを関数gで暗号化し、暗号文e =g(d)=g(f(c))=f(g(c)) をAに送り返す…ここのところ、暗号文の暗号化であり、本方式の絶妙テクニックである。
Aは、この暗号文eを逆関数f- 1 復号化、z = f- 1 (e) = g(c) としてこれを再びBに送る。
そこでBは、 z を逆関数g- 1 で復号化、元の平文c を手に入れることが出来る。
見事なものだ、復号化するための逆関数を「AとBは共有していない」のに、Bはちゃんと復号が出来ている!

========================

以上、ほんの一欠片には過ぎぬが拙くも引用してみた。
数学思考の強化に充てるもよし、またゲームデザインのヒントに活かすもよし、これまで以上に数学を憎むもよし、とりわけ学生諸君には、僕の代わりに一問一問ぶっつかってゆくことを祈念しつつ、僕自身はもう当分は数学には手出ししないでおこうと思う。
なお、本書は初版が2014年末で、既に続編本も出ているようである(やはり超難問数学パズルのヴァラエティに富んだ連弾集だそうで)。

謝辞

ここに提示の記事は、いずれも私自身の判断責任のもと編集・投稿したものです。

大半の投稿は学生など若年層向けを意図してやや平易な表現にて、通俗性は極力回避しつつ、論旨の明示性を重視しつつ書き綴りました。あわせてまた、社会人の皆様にお読み頂くことも想定しつつ、汎用性高い観念知識を相応に動員しながら記した積もりです。

私なりの思考着想によるささやかな閃きが、皆様の諸活動にて何らかの光源たり得れば、望外の喜びであります。

山本