Comments
Description
Transcript
プログラマのための論理パズル：難題を突破する 論理
プログラマのための論理パズル：難題を突破する 論理思考トレーニング Puzzles for Programmers and Pros Dennis E. Shasha 著 吉平健治訳 2015 年 9 月 17 日 Original English language edition: Puzzles for Programmers and Pros by Dennis E. Shasha Published by Wiley Publishing, Inc. Copyright © 2007 by Dennis E. Shasha Japanese translation published under license by Ohmsha, Ltd. Copyright © 2009 by Ohmsha, Ltd. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, without the prior written permission of the publisher. 本書を発行するにあたって、内容に誤りのないようできる限りの注意を払いましたが、本書 の内容を適用した結果生じたこと、また、適用できなかった結果について、著者、出版社とも 一切の責任を負いませんのでご了承ください。 本書に掲載されている会社名・製品名は一般に各社の登録商標または商標です。 本書は、「著作権法」によって、著作権等の権利が保護されている著作物です。本書の複製 権・翻訳権・上映権・譲渡権・公衆送信権（送信可能化権を含む）は著作権者が保有していま す。本書の全部または一部につき、無断で転載、複写複製、電子的装置への入力等をされると、 著作権等の侵害となる場合がありますので、ご注意ください。 本書の無断複写は、著作権法上の制限事項を除き、禁じられています。本書の複写複製を希 望される場合は、そのつど事前に下記へ連絡して許諾を得てください。 • オーム社書籍編集局「プログラマのための論理パズル：難題を突破する論理思考トレー ニング」係宛、E-mail（[email protected]）または書状、FAX（03-3293-2824） にて iii 訳者まえがき Translator Preface この本は、次のような人に向けたパズル集である。 • プログラマとしての力を伸ばしたい人 • ソフトウェア開発職でより良いポジションに就きたいと考えている人 • 優れたプログラマを採用したいと考えている企業とその採用担当者 パズルだからと甘く見てはいけない。この本は、よくある論理パズル集とは違っ て、プログラマの思考力を鍛える選りすぐりのパズルを集めて、それを解く道筋を示 している。より良いプログラマを目指す人にとっては、きっと役に立つだろう。 今後ますます重要になるソフトウェア産業において、優秀な人材であるみなさんに は、いっそう力を磨きつつ、適切なポジションを得て活躍してほしい。また企業はそ のような人材をうまく取り入れて力としてほしい。この一風変わったパズルの本がそ の一助となれば幸いだ。 2009 年 3 月 プリンストンにて 吉 平 健 治 iv 著者について About the Author Dennis E. Shasha 氏は、ニューヨーク大学クーラン数理科学研究所コンピュータサ イエンス学科で教授職を務める。研究分野は多岐にわたり、生物学の分野では DNA マイクロアレイにおけるパターン発見問題、組み合わせデザイン問題、ネットワーク 推定問題に取り組む一方、物理学そして金融工学においては時系列データ解析アルゴ リズムやデータベースアプリケーションも研究対象としている。さらには、データ ベース性能チューニングやツリー/グラフマッチング問題にも取り組んでいる。 筆まめであることから、本書の他にパズル関連の書籍を 5 冊、コンピュータサイエ ンティストにまつわる逸話を収めた伝記、データベースチューニング、生物学におけ るパターン認識、時系列データ分析に関する著書を出版。加えて、50 以上の学術雑 誌論文と 60 以上の学会論文を発表、そして 7 つの特許を取得している。趣味として、 Scientific American[Sci ] のウェブ版や Dr. Dobb’s Journal[Uni ] でパズルに関するコ ラムを不定期に連載している。 To omniheurists from every corner of the earth v 謝辞 Acknowledgments まずはじめに、私のパズルに挑戦するすべて読者の方々にお礼を申し上げたい。読 者は南極以外のすべての大陸に渡り、コミュニケーションを通じて、お互い新しい知 性を見つけることができた。読者の中には友人になったものもいる。素晴らしい教師 であり数学者でもある Andy Liu、抑えきれないほどの創造力を持ち合わせた建築家 の Mike Whittaker。私が編み出したパズルが、彼らとのコミュニケーションを通じ て、新たに生まれた疑問を連れて私に戻ってくる。そのとき、パズル自体にひねりが 加わる。結果、私でも解けないくらいのパズルになってしまったとき、私はそのパズ ルを「ブレイン・トラスト」 （ブレーン、相談役、顧問団）と呼ぶことにしている。数 学的に、計算的に困難な問題に直面したとき、このような天賦の才能を持った方々と 侃々諤々議論を交わしてきた。そして、新しい解法を見つけてきたのだ。 Scientific American 編集部の John Rennie 氏、John Erickson 氏、Dr. Dobb’s Journal の Deirdre Blake 氏には、これらパズルの編集にあたり多くの助言をいただいた。私 がパズルを実際に書き下ろした後、初めて目を通してくれたのがこれらの方々だ。私 の文章表現の中にある曖昧さを見つけ出し、パズルをより明確にしていただいた。ま た、口頭でパズルを提案したものもある。Tyler という若者はそれらのパズルを聞い ては、（多少のヒントを使って）解答を導き出すだけでなく、lame（つまらない）な ものか、ill（cool。イケテイル）なパズルかを判定してくれた。 Gary Zamchick 氏からはイラストを提供してもらい、パズルに装飾をしてもらっ た。彼のちょっとした筆遣いでパズルのエッセンスを搾り出す才能には、目を見張る ところがある。 本書の出版にあたり、担当いただいた Carol Long 編集委員、担当編集の Sara Shlaer 氏、校正担当の Mildred Sanchez 氏、装丁の LeAndra Hosier 氏にも感謝を申し上げ たい。視覚表現、文章表現に対する私の強い要望にも十分対応していただいた。本書 がよい評判をいただくことになれば、それはこれらの編集者の方々の努力の結果で ある。 目次 vi 目次 訳者まえがき iii 著者について iv 謝辞 v 日本語版に寄せて：パズルはソフトウェア開発に役立つ ix イントロダクション 第I部 マインド・ゲーム 競争：みなが勝者になれるわけじゃない . . . . . . . . . . . . . . . . . . . . 甘いもの好き . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ビザンチン流ギャンブル . . . . . . . . . . . . . . . . . . . . . . . 幸運の感触 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii 1 3 4 8 11 インフォメーション・ゲイン . . . . . . . . . . . . . . . . . . . . 天まで届け！ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 助成金のための政治 . . . . . . . . . . . . . . . . . . . . . . . . . 14 17 19 社会派ゲーム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 26 逃亡マネージメント . . . . . . . . . . . . . . . . . . . . . . . . . インフルエンザの数学 . . . . . . . . . . . . . . . . . . . . . . . . デザイン：想像力に導かれて…… . . . . . . . . . . . . . . . . . . . . . . . . 氷上の鞭使い . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 最高の業界用語 . . . . . . . . . . . . . . . . . . . . . . . . . . . . ビー玉のプレゼント . . . . . . . . . . . . . . . . . . . . . . . . . 反転する色 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 伝統的な対戦日程 . . . . . . . . . . . . . . . . . . . . . . . . . . . フラクタル生物学 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 31 32 36 39 41 43 45 vii パイの子供カット . . . . . . . . . . . . . . . . . . . . . . . . . . . チャンス：真の幸運を掴め . . . . . . . . . . . . . . . . . . . . . . . . . . . ラッキールーレット . . . . . . . . . . . . . . . . . . . . . . . . . 法律の論理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ボックスチップゲーム . . . . . . . . . . . . . . . . . . . . . . . . フィードバックの比率 . . . . . . . . . . . . . . . . . . . . . . . . 推論：何を考えているの？ . . . . . . . . . . . . . . . . . . . . . . . . . . . 数字の手掛かり . . . . . . . . . . . . . . . . . . . . . . . . . . . . マインド・ゲーム . . . . . . . . . . . . . . . . . . . . . . . . . . . 拒否しても暴露 . . . . . . . . . . . . . . . . . . . . . . . . . . . . マッド・ミックス . . . . . . . . . . . . . . . . . . . . . . . . . . . 最適化：Doing more with less . . . . . . . . . . . . . . . . . . . . . . . . . . そこ掘れ！ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 嗜好でロマンス . . . . . . . . . . . . . . . . . . . . . . . . . . . . ホリデーではお釣りはだめよ . . . . . . . . . . . . . . . . . . . . 深海では静かに . . . . . . . . . . . . . . . . . . . . . . . . . . . . 第 I 部の解答 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 第 II 部 パズルには何が隠されているか 48 51 52 54 59 63 67 68 70 74 77 79 80 82 86 88 90 157 年齢並べ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 都市計画 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 時間どおりに仕事を終わらせるには？ . . . . . . . . . . . . . . . 167 宝の在処をピクチャリング . . . . . . . . . . . . . . . . . . . . . . 168 SUDOKU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 数字へエンコード . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 選り好みする貪欲 . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 甘いもの詰め合わせ . . . . . . . . . . . . . . . . . . . . . . . . . 189 再訪する巡回セールスマン . . . . . . . . . . . . . . . . . . . . . . 191 過負荷スケジューリングと結晶冷却 . . . . . . . . . . . . . . . . . 198 ワードスネーク . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 最高の友達 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 勝利のスロット . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 サイコロを理解する . . . . . . . . . . . . . . . . . . . . . . . . . 214 囮に惑わされず . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 viii 目次 第 II 部の解答 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 参考文献 237 索引 238 訳者あとがき 241 • 本書のパズルを解く際に使う図・データ・テキスト類、別解答情報、正誤情報などにつ いては、オーム社ホームページ（http://www.ohmsha.co.jp/）の「書籍連動／ダウ ンロードサービス」にて公開しています。 • 上記サービスは、止むを得ない事情により、予告なく中断・中止する場合があります。 ix 日本語版に寄せて：パズルはソフ トウェア開発に役立つ Introduction for Japanese Edition*1 考える力の大切さ 人間にとって、考える力は最も大事なものの一つだ。豊かな人生を有意義に過ごす ための基本的な能力といえる。もちろんビジネスにおいても、学校での学習や受験に おいても欠かせない。 ビジネスシーンでは、「仮説思考力」など、人間の思考に関する各種の方法論が提 唱され、実践されている。それらの思考法がいずれも共通して目指しているのは、柔 軟な発想と応用を可能にする一般思考力を高めることだ。 思考力を高める目的は、ビジネス上の課題、問題を効率良くより多く解決すること にある。そして一般的なビジネスシーンだけではなくて、プログラムという論理的な 制御を記述するソフトウェア開発では、考える力はいっそう重要になる。後で述べる ように、優れたソフトウェアを作るには思考力の中でも、より高い発想力が必要とさ れる。 考える力を鍛えることの難しさ しかし、考える力を鍛えるのは楽ではない。これにはいくつかの理由がある。 まず、思考力を鍛えるための方法には王道がない。能力を身に付けるためには、ト レーニングを繰り返す以外にない。どの方法も、頭で理解するだけでなく、訓練を通 して身に付ける必要がある。 *1 訳注：このイントロダクションは日本語版発行にあたり訳者により追加された。 x 日本語版に寄せて：パズルはソフトウェア開発に役立つ 次に、思考力を身に付けるための方法が、それを必要とする人たちに十分に知られ ていない。「知識を得る」には、書籍を読む、上司・先輩に助言を求める、セミナーに 参加するといった方法があり、これらは誰でもできる。しかし、本書で紹介するパズ ルのように、得た知識を「吸収」して自分のものにし、現実問題に応用する方法は、 十分に広まっているとはいえない。 もし、吸収する方法を知っていたとしても、それを実行しにくい。業務を通じて経 験で習得していくのが一番現実的な方法だが、そもそもそういった職に就くことが簡 単ではないし、業務によって応用分野が限られてしまう。 しかも、できれば短期間で、退屈な繰り返しを避けて楽しみながら身に付けたいと 思うのが人の性だが、そのような条件を付けると方法はかなり限られる。 パズルは思考力のトレーニングに最適 このような問題を解決するのに効果的なのが、この本で紹介するようなパズルだ。 パズルは誰にでも挑戦でき、楽しみながらトレーニングできる。楽しさは動機になる し、学習効率も良くなる。人間は本来、遊んでいるときがリラックスしつつも集中力 は非常に高くなり、感受性も上がるといわれている。パズルはこの状況を自分の中に 作り出すのに最適な方法だ。 ではなぜプログラマの思考力を鍛えるのにパズルが、しかも難易度が高いものが適 しているのか。それは、優れたソフトウェアを作るには、特に高い発想力が必要だか らだ。 ソフトウェアを開発する目的は、作業を自動化するシステムのような一般的なもの から、営業マンをどのように配置すれば最も売り上げを伸ばすことができるか、フラ ンチャイズ店が新しく支店を構えるとしたらどこが最適かというアルゴリズムの実装 など幅広い。これらの開発で共通しているのは、どれも「明確な設計方法や答はすぐ には導けない、もしくは明確な設計方法や答が存在しない」ということだ。現実世界 では、私たちはそのような問題に何らかの道筋や回答を見つけなければならない。自 動化システム開発の場であっても、性能や効率がよく高品質を保つソフトウェアを 設計する決まった答は存在しない。そのためには、公式を覚えて当てはめるのではな く、頭を使う必要がある。頭を使う難しいパズルは、まさにこういった問題を解くた めのトレーニングとして最適なものだ。優れたソフトウェアを作るための思考力を鍛 えるには、パズルが役に立つ。 ソフトウェア開発の要素を具体的に見ていこう。 xi •「機能・要件定義」では、提示された問題を深く観察・理解し、開発すべき目 的を明確にしなくてはならない。これはパズルの題意を理解することに相当す る。パズルの初期状態、制約条件、目標の状態を正確に理解しない限り、そも そもパズルに挑戦することができない。また、最適解ではなくても落としどこ ろをどのあたりに定めるかという現実問題に対応する能力も問われる。 •「設計」は、パズルを解く手法そのものに相当する。アルゴリズムが性能に大 きく影響するし、パズルで必要となる次のケース・ステップをくまなく調べ上 げる力は、機能要件を実装設計に落とし込む段階で品質の確保に大きく貢献で きるはずだ。 •「コーディング」では、同様にアルゴリズムのひらめきが重要だし、さらにパ ズルでの制約条件を正確に見抜く力は、コードレベルでの例外処理を網羅し、 高品質を保つには不可欠だろう。 •「テストケース作成」では、解法の仮説を立てて仮の回答を導く力が、テスト ケースのカバレッジに生かされるはずだ。 •「デバッグ」における、限られた情報から隠れた本質を導き出す作業は、まさ にパズルにおけるケース分析に等しいといえる。 一般的な論理パズルは、このような力を鍛えるのに最適だとはいえない。 一方、この本のパズルは、プログラマの能力を試し、鍛えるのに特に適したものば かりを集めている。コンピュータサイエンスでよく知られた技法のいくつかを現実の 問題に当てはめた実例も、その思考過程も含めて掲載されている。 パズルと採用・人事 優れたプログラマを目指している人だけでなく、優れたプログラマを探している人 にとっても、パズルは役に立つ。なぜならこの本にあるようなパズルは、プログラマ の力を測るテストとしても有用だからだ。特にパズルは、解いている人の思考過程を 観察できるという特長がある。 パズルは、人材の適性をより深く測り、有効活用するのに役立つ。現実の仕事に近 い状態での適性を見るので、通常の適性検査や年齢などだけに頼った場合よりも、よ り適切な配置ができ、人材を生かすことができる。 また、パズルの楽しさを生かして、知的好奇心も調べられる。与えられた困難な問 題に対し目を輝かせて挑戦してくる姿勢というのは、普遍的に大切なスキルセット だ。そのような意識チェックにもパズルは使える。 xii 日本語版に寄せて：パズルはソフトウェア開発に役立つ このような採用におけるパズルの有効性というのは経験的に実証されており、特に 著者および訳者が生きているアメリカの IT 社会では、採用におけるパズル出題は常 識となっている。Microsoft や Google をはじめ、アメリカの IT 企業はソフトウェア エンジニアの人材の発掘に非常に多くのお金と時間をかけている。学生が就職する場 合、希望する部署の担当者や上司が学生と直接面接し、時には数日もかけて念入りに 候補者の能力を測定し、ポジションとのマッチングを行う。エンジニア個人の能力が 企業の生産性に直結していること、そしてその生産性・コスト比率は線形以上の関係 であることが確かめられているからだ。 もちろんパズルは万能ではないし完璧でもない。しかし現実に、ソフトウェア大国 であるアメリカにおいて、パズルを効果的に利用して実績を上げている事例があるこ とは注目に値するし、学ぶものがあると筆者は考える。ここでの説明はこれくらいに しておこう。それでは Shasha 教授のパズルを存分に楽しんでほしい。 吉 平 健 治 xiii イントロダクション 世界的に名が知られている、とあるインターネット企業の採用面接を受けた。 その企業は採用試験官がパズル的思考を必要とする難しい質問を面接で使うこ とでも有名だ。でも、Shasha 教授の授業を受けた後の面接だったので、どの質 問も朝飯前だったよ。 ―― ―ニューヨーク大学で私の授業の卒業生の一人、Boris*2 世の中には、心からパズルが好きな人がいる。私もその一人。一方、プログラマに なるための就職活動としてパズルを勉強している人もいる。今回手がけた拙著は、こ のどちらの人にも役に立つはずだ。パズル好きの人は、ぜひ本書に収めたパズルその ものを楽しんでもらいたいが、その他にも、どのように問題解決に挑むのか、その解 法の手引きも解説してみた。これは、一般的な問題解決法を学ぶことで、新しいパズ ルや問題に出会った時にも対応できることを、読者に分かってもらいたいために執筆 した。就職面接にも絶対に役に立つ。 さて、そもそも就職面接でパズルを使うことを否定する意見もある。その批判の根 拠には、ほとんどのパズルの問題というのが現実から離れていることが挙げられてい る。確かに、私が作るパズルの設定は、実際私たちが解かなくてはならない問題とは 異なっている。しかし、現実の問題を「基にして」生まれてきたものばかりだ。見た 目は異なってはいるが、現実問題のエッセンスを抽出したのだ。実際、私の本職の研 究においては、本来の研究課題を抽象化したパズルに置き換えることは常套手段であ る。問題の基本をなす要素、つまり問題の本質を見つけやすくするためだ。本質以外 に問題を飾り付ける些細なことは後ほど考えればよい。この方法で今まで多くの研究 課題を克服できているのは、私の経験が物語っている。そう、私にとって洗練された パズルというのは、科学的にもエンジニアリング的にも問題の実態・真相を暴く素晴 らしい手段でもあるのだ。 *2 訳注：Boris は 2004 年当時、訳者と共に Shasha 教授の授業を受講していたクラスメイトである。 とある企業とは、世界最大のインターネット検索サービス会社で、彼は現在、そのマンハッタンオ フィスに勤めている。 イントロダクション xiv それでは、なぜ私は他人のためにパズルを作るのだろうか？ それは、まずパズル 自体が楽しいものだからだ。みんなにパズルを楽しんでもらいたい。もう一つの理由 は、みんなにパズルを使って、脳を活性化させてほしいのだ。私はニューヨーク大学 で冒頭の Boris の引用で紹介した授業を受け持っている。そこでは、私が作成した問 題に挑戦するために、毎週学生はプログラムを書いてこなくてはならない。作成され たプログラムは学生同士で競い合い、勝者は KitKat バー（チョコレートのお菓子）が もらえる。 授業中、私は、いわゆる「講義」をほとんどしない。その代わり、パズルを解くテ クニックを披露する。問題の「解答」ではなく、「解法」を紹介するのだ。本書の第 II 部では、このテクニックを十分に紹介したい*3 。 面白いことに、学生たちはその週の授業を終えると、自分の問題解決能力が向上し ていることに驚く。授業を通して得られた体験が、現実問題への取り組み方の一部な のだ。授業で扱う問題は、アルゴリズム理論の教授に言わせてみればすべて「扱い不 能」である。しかし、教授が何と言おうと、現実問題として何としても解かねばなら ないのだ*4 。授業中、学生たちの頭の中でどういった変化が起きたのか、どういった 体験をしているのか、私には正確に答えることはできない。でも、学生たちは脳をフ ル回転させた。その結果、彼らの思考パターンに変化が起きたことは確かである。 第 I 部の大部分は、Scientific American*5 や Dr. Dobb’s Journal*6 の私のコラムに掲 載したパズルを、多くの読者からいただいた大切な意見・感想を考慮し、単行本用に 変更、さらに問題を追加し、より複雑にしたものだ。なので、既にこれらの雑誌でパ ズルに挑戦された方も、再度試みてほしい。 パズルに行き詰まった時、私はとにかく紙に何かを書き込むようにしている（自分 が作成したパズルでも、ときどきその解き方が分からなくなるが……）。最初に紙に 書き込んだやり方というのはたいてい間違っている。しかし、正解に導くためのアプ ローチであることには間違いない。 *3 訳注：Shasha 教授は、Dr. Ecco（ドクターエッコ）という天才が難問パズルを解決しながら活躍す る推理小説型のパズル集を単行本や雑誌記事で発表している。原著には第 III 部として、この Dr. Ecco を題材とした小説パズルが収録されているが、日本の読者にはこのシリーズに馴染みが薄いこ と、小説内のパズルには出題提示のみで解答がないこと、Shasha 教授に直接解答を提案する懸賞パ ズルであったことから、日本語版では割愛させていただいた。 *4 訳注：ニューヨーク大学の学生は、社会人が働きながら学んでいることが多い。キャリアアップの ために学位を取得することを目指して授業を受けているのだ。 *5 訳注：サイエンティフィック・アメリカン [Sci ]。米国の著名な一般向け科学雑誌。 *6 訳注：ドクター・ドブズ・ジャーナル [Uni ]。米国のコンピュータプログラマ向け雑誌。 第I部 マインド・ゲーム Mind Games このパズルを解けたなら、あなたは管理職向きの人材ではない。頭が切れすぎる。 注意：特に難しいパズルには、この頭を抱えたアイコンが付いている。 競争 3 競争 Competition みなが勝者になれるわけじゃない • 甘いもの好き（p. 4） • ビザンチン流ギャンブル （p. 8） • 幸運の感触（p. 11） • インフォメーション・ゲイン （p. 14） • 天まで届け！（p. 17） • 助成金のための政治（p. 19） • 社会派ゲーム（p. 21） • 逃亡マネージメント（p. 26） • インフルエンザの数学（p. 28） 4 第I部 マインド・ゲーム 甘いもの好き Sweet Tooth ケーキと数学が大好きな 2 人の子供たち、ジェレミーとマリーがここにいる。きっ と、あなたの傍にもこんな子供たちがいるに違いない。さて、ジェレミーが次のよう なゲームをしようとマリーに話を持ちかけてきた。マーティンがこしらえた 2 つの全 く同じ形をした四角いケーキを使ったゲームだ。 まず最初にジェレミーが 1 つ目のケーキを 2 つに切って分けるとする。ジェレミー は 2 等分するかもしれないし、そうしないかもしれない。次に、これを見たマリー が、自分が 1 つ目のケーキで最初に選択権をとるか、もしくはジェレミーに選択権を あげるか、それを決めることができる。このルールでの選択権とは、切り分けられた ケーキを選ぶ権利のことだ。なお、切り分けられたケーキの大きさは異なるかもしれ ない。もし、マリーが最初に選択権を行使すれば、当然彼女は 1 つ目のケーキの 2 つ に分かれた大きいほうを食べるに決まっている。もし、選択権をジェレミーに譲り、 自分の選択権を 2 つ目のケーキを切るときまでとっておけば、1 つ目のケーキでは きっとジェレミーは大きいほうを取るに決まっていると、マリーは推測するだろう。 さて次に、ジェレミーは 2 つ目のケーキを、また 2 つに切り分ける。ここで注意し てもらいたいのは、ジェレミーはどんなふうにでも切り分けることができるというこ とだ。1 つ目のマリーの選択の場合によっては、限りなく小さいかけらのケーキを切 り分けることもできるだろう。1 つ目のケーキの選択権をどちらが取るかで、状況は 単純に 2 通りの可能性がある。つまり、もしマリーが 1 つ目のケーキで大きいほうを 取った場合、2 つ目のケーキではジェレミーに選択権があるので、そこでは大きいほ うを取る。もし、1 つ目のケーキでマリーが選択権をジェレミーに譲った場合、彼女 は 2 つ目のケーキでは大きいほうを選ぶだろう。 ウォームアップ問題 P3 ジェレミーもマリーも、2 つのケーキからできるだけたくさん食べたいとしよ う。ジェレミーにとって、このゲームを攻略する最善の戦法は何だろうか？ ヒント：まだ、次ページの解答を見ないように。1 つのケーキの大きさを 1 としたと き、ジェレミーが 1 つ目のケーキを、 f と 1 − f の割合で切り分けたと考えてみよう。 f のほうが大きいとする。つまり、 f は最低でも 1/2 だ。そうすると、マリーが選ぶ のは、1 つ目のケーキで大きい f のほうを取るか、まずは小さい 1 − f を取り 2 つ目 のケーキで大きいほうを取るかのどちらかだ。 甘いもの好き 5 ウォームアップ問題の解答 ヒントをもとに考えてみる。マリーの立場に立つと、彼女は次のように推論する はずだ。もし、1 つ目のケーキで選択権を行使し、自分が大きい f のほうを取れば、 ジェレミーは 2 つ目のケーキを丸ごといただくだろう。なぜなら、ジェレミーは、0 に限りなく近いケーキのかけらと、ほぼ丸ごとの大きさに近いケーキに切り分けるこ とができる。そして、当然、大きい丸ごとのほうを取るのだ。すなわちこの場合、1 つ目と 2 つ目のケーキを合わせ、マリーは f だけ、ジェレミーは (1 − f ) + 1 の大き さのケーキを得ることができるわけだ。 逆に、もし 1 つ目でマリーが選択権を行使しなかったらどうだろう。マリーは 1 つ 目のケーキで 1 − f 分を取る。2 つ目のケーキではマリーに選択権があるので、ジェ レミーは 2 つ目のケーキを 2 等分にするだろう。大きいほうを選択するマリーの取り 分を最小限にするためだ。マリーは最終的に (1 − f ) + 1/2 を得ることとなるわけだ。 そこで、ジェレミーの戦略はどのようになるだろうか。マリーの取り分を最小にす るためには、上記の 2 つの場合でマリーが得られる分を等しくすればよい。つまり、 f = (1 − f ) + 1/2 を満たす f が、ジェレミーにとって最適な切り分け方となるのだ。 上記の式を解けば、すぐに f = 3/4 だと分かる。 それでは、本当にベストな戦略か確認してみよう。ジェレミーが、1 つ目のケーキ を f = 3/4、つまり 3/4 と 1/4 に分けて切る。1 つ目のケーキでマリーが選択権を とった場合、ジェレミーは 1/4 を 1 つ目のケーキから、2 つ目のケーキでは丸ごと、 つまりジェレミーは全部で 1 41 分のケーキが食べられる。一方、1 つ目のケーキでマ リーが選択権をジェレミーに譲ったとしても、ジェレミーは 1 つ目のケーキで 3/4、 2 つ目のケーキで最低 1/2、トータルでやはり 1 14 分のケーキが食べられる。逆に、マ リーはどのように選択権を行使しても、2 つのケーキから 3/4 分しか取ることができ ないのだ。 さらに、 f がどのように影響を与えるか、もう少し考えてみよう。もし、ジェレ ミーが 3/4 より小さい割合で 1 つ目のケーキを切り分けたらどうなるだろう。当然、 マリーは 1/4 より大きい分 1 つ目のケーキから得ることができる。でも、2 つ目の ケーキからは、やはり最大 1/2 しか得ることができない。 f が 3/4 より少なくなった 分だけ、マリーの取り分が 3/4 から増えるわけだ。逆はどうだろう。ジェレミーが 3/4 より大きく f をとった場合だ。マリーが、1 つ目のケーキの f 分だけいただける ので、この場合でもジェレミーが選んだ f の 3/4 より大きい分が、マリーの取り分 3/4 に加えられることとなる。 6 第I部 マインド・ゲーム 図 1.1 f の違いによるマリーの取り分の変化。いずれの場合をマリーが選択して も、交差点である f = 3/4 のときにマリーの取り分は最小になる。 甘いもの好き 7 さて、ウォームアップ問題では、かなり細かく解説させてもらった。なぜなら、よ り難しい問題が 1 週間後にやってきたからだ。今度は、シェフのマーティンは 3 つの ケーキを準備してきたのだ。ジェレミーとマリーはよだれが垂れんばかりだ。ちなみ に、3 つのケーキの大きさはもちろん四角くて等しい。 ジェレミーとマリーは、またしても次のようなルールを決めた。今度も 1 週間前と 同様、ケーキは 3 つともジェレミーが切ることとする。ただし、今回はマリーは選択 権を 2 回行使できることとする。ジェレミーの選択権行使は 1 回だけ。つまり、ジェ レミーは 1 つ目のケーキを切る。マリーはここで選択権を行使して大きいほうを取る か、行使せずジェレミーに大きいほうを取らせるか選ぶことができる。2 つ目のケー キ、3 つ目のケーキでも同様だ。マリーは必ずジェレミーに最低 1 回は選択権を与え なくてはいけない、というのが唯一の条件だ。 問題 1. さて、このようなルールの下、ジェレミーはどのようにすれば、より多くの ケーキを食べることができるだろうか？ 最大どれくらいの割合のケーキを 食べることができるだろうか？ 問題 2. では、もしも、7 つのケーキが準備されていたらどうだろう？ ルールはマ リーが 7 つのうち 6 つのケーキで選択権を行使できるとする。この条件で は、ジェレミーとマリーのどちらが、そしてどれだけ有利になるだろうか？ 問題 3. ジェレミーがすべてのケーキを切り続けるとして、ジェレミーとマリーが全 く等しい分量のケーキを食べられるような、そんな方法は実際に存在するだ ろうか？ 3 （解答は p. 90） P 8 第I部 マインド・ゲーム ビザンチン流ギャンブル Byzantine Bettors ビザンチン帝国と聞くと何を思い浮かべるだろうか。（城のある国々の例外にもれ ず）宮廷内で絶え間なく繰り返された悪事と陰謀の帝国、というところだろうか。当 然ビザンチン帝国の歴史は繰り返されてはならない。現代の歴史研究においては、ビ ザンチン帝国が最初に築き上げた千年の美しき平和、という偉業のほうがむしろ注 目されているようだ。歴史は繰り返される。このパズルはそんなビザンチン帝国の陰 謀の数々に思いをはせて考えたものだ。ビザンチン流ギャンブル、とでも呼ぶとし よう。 ビザンチン流ギャンブル 9 ゲームの賭けは次のように行う。何人かの「アドバイザー」と呼ばれる助言者と、 挑戦者であるあなたがいる。一人のアドバイザーは 1 か 0 の数字を紙に書き、他の アドバイザーに見せる。しかし、あなたには見せないようにしてあなたの目の前に紙 を伏せて置いておく。4 人のアドバイザーはそれぞれあなたに向かってその紙に何が 書いてあるのかを教えてくれるのだが、みなかなりの役者で、その真偽は表情からも 読み取ることができない。1 回につき賭けることのできる額は、0 から所持金全額ま でだ。 ウォームアップ問題 P3 では、4 人のアドバイザーがいたとして、そのうちの 2 人はいつでも真実を伝え てくれるとする。だが、その 2 人とはいったい誰であるのかは分からない。あなたは 3 回の賭けに挑戦できて、$100 の所持金を持ってゲームを始めるとしたら、最低いく らまで確実に所持金を増やすことができるだろうか？ 賭けの比率は一対一で、数字 を当てることができたら賭けた金額だけ相手からもらえる。負ければ、賭けた額が没 収される。 ウォームアップ問題の解答 もし、4 人のアドバイザーのうち、4 人ともまたは 3 人が同じ答えをしたとしたら 全額賭けるとよい。真実を伝えるアドバイザーはこの 3 人のうちの 2 人だ。また、4 人の答が 2 人ずつに分かれていたら、賭けをしないほうがよい。いずれにせよ 1 回目 の賭けで、どの 2 人が本当のことを言ってくれるアドバイザーかが分かる。なので 2 回目以降は最高額をつぎ込むことができる。ということで、少なくとも 2 回は全額賭 け、必ず勝つことができる。つまり、最終的に合計額$400 まで所持金を増やすこと が可能だ。 問題 1. 本題に入ろう。3 人のアドバイザーがいて、そのうち 1 人がいつも真実を伝 えてくれる。今回も賭けは 3 回で所持金は$100。この場合、最低いくらまで 確実に所持金を増やすことができるだろうか？ 第 I 部 マインド・ゲーム 10 さて、このゲームはかなり意地悪なルールに変わってしまった。今回は 4 回の賭け をするのだが、もはや真実を伝えてくれる人物は存在しない。その代わり気まぐれで 真実を言うアドバイザーがいる。このアドバイザーは、いつでも必ず真実を教えてく れるわけではない。4 回のうち少なくとも 3 回は教えてくれるというのだ。それ以外 の 3 人の嘘つきはどのような答を出すか分からない。真実であることもあるし、そう でない場合もある。さらに加えて、あなたの賭けを聞いた後で、アドバイザーは紙の 中身をあなたが不利になるように書き換えることができる。しかし、書き換えること で、気まぐれで真実を言うアドバイザーが 4 回の賭けの結果 1 人もいなくなってしま うようなことがあれば、書き換えることはできない。 問題 2. 4 回の勝負で最低いくら勝つことができるだろうか？ 今回は、アドバイザー は 4 人いて、そのうち 3 人は嘘つきだ。4 回のうち最低 3 回は本当のことを 教えてくれる気まぐれなアドバイザーは 1 人いる。 問題 3. 次のように少し有利に条件が変わったらどうだろうか？ 5 回のうち最低 4 回は本当のことを教えてくれる、気まぐれなアドバイザーが 1 人、3 人の嘘 つきがいる。5 回の賭けで、最終的に少なくとも$150 を手にすることはでき るだろうか？ 3 （解答は p. 92） P 幸運の感触 11 幸運の感触 A Touch of Luck 映画『10 億分の 1 の男』[Fre01] は、強運な人というのは生まれながらにしてラッ キーなのだ、と物語っている。ラッキーな人はギャンブルでもついているし、交差点 の信号待ちでさえもいつも運に恵まれている。でもそんな強運の持ち主は、運を盗む 人との身体接触を避けなくてはならないようだ。なぜなら、彼らは運の盗み方を心得 ていて、強運である他人の体に触ることで運を盗んでいく。強運の人を見つけ出すこ とこそが、映画の中で主人公が追い求めていることだ。彼は、そんな強運の持ち主を 見つけ出すために、とある実験をした。強運の持ち主かもしれないその可能性のある 人たちを、目隠しをさせて森の中を走らせた。一番最初に目的地に着いた人が強運の 持ち主というわけだ。しかし、それ以外の大多数は木にぶつかってしまうだろう。 私たちは肉体的にもう少し手荒くない方法で、強運の主を探してみたい。ここで N 人の人で B 回の賭けをするゲームの機会を設定した。プレイヤーはみな N と B の値 を知らされていて、ある程度の所持金（全員同額というわけではない）を持ってス タートする。 賭けの内容は、種も仕掛けもないコインを投げて、出たコインが裏か表かによって 勝負を決める。賭け方は一対一方式である。つまり、賭け金 x に対してコインの表裏 を当てた場合さらに x もらえて、負けたら賭け金 x はそのまま没収されるという方式 である。 また、コインが投げられる前に、プレイヤーは全員次に出るコインの表か裏かにそ れぞれ好きなだけの額（0 から所持金全額まで）を賭けることができる。 B 回の賭けが終わった時点で、所持金を一番多く持っているプレイヤーがこのゲー ムの優勝者で勝者となる。もし 2 人が同額となったら、誰も勝者にはならない。すべ ての賭けが終了した時点で、優勝者以外の所持金は無効となる。つまり、勝者一人だ けがお金を手にできるのだ。 ウォームアップ問題 1 P3 Bob と Alice は同額の所持金を持っている。Bob が先に賭け金を提示しなければ ならない。残りのゲーム回数はあと 1 回のみ。Alice の勝率はどのくらいだろうか？ 12 第 I 部 マインド・ゲーム ウォームアップ問題 1 の解答 もし Bob がコインの表に x だけ賭けたら、Alice は同じくコインの表に x + 1 の額 を賭ければよい。Alice は出たコインが表であれば勝つわけだし、逆に裏が出たら負 けるわけだ。他の方法としては、Alice は何も賭けないやり方がある。裏が出た場合、 Alice が Bob に勝てる。いずれにせよ、この状態では Alice の勝率は 2 分の 1 である。 ウォームアップ問題 2 P3 今回もまた、Alice と Bob だけで勝負する。Alice は Bob よりも所持金が多い。 残りの勝負はあと 5 回。もし毎回 Bob が Alice よりも先に、裏か表どちらにどれだ け賭けるかを宣言しないといけないとする。この条件で、Alice はどのようにして勝 率を上げることができるか？ ウォームアップ問題 2 の解答 Alice はゲームに必ず勝つことができる。毎回の勝負で Alice はただ単純に、Bob のやることを真似すればよいわけだ。つまり、Bob が表に b だけ賭けたら、Alice も また表に b だけ賭ければよい。結果コインが表に出ようが、裏に出ようが、Alice は 最終的に Bob に勝つことができる。 さてさて、いよいよ本題に入る。 問題 1. Bob と Carol、そして Alice の 3 人のプレイヤーがいる。Alice は 51 の所持 金を持っている。それに対して、Bob と Carol は 50 ずつだ。コインの表か 裏のどちらか、またいくら賭けるのかを Bob は一番最初にみなに伝えなけ ればならない。Bob の後で Carol、そして Alice の順番で自分がどのように 賭けるかを宣言する。実は Bob と Carol は共謀していて、どちらかが勝て ば賞金を山分けすると口裏を合わせてある。賭けの回数は残り 1 回だ。Bob と Carol はいずれかが勝つ可能性を最大限広げるにはどうしたらよいだろ うか？ 問題 2. 問題 1 で最初に Alice が、表裏どちらにいくら賭けるかを伝えるとしたら、 勝敗の結果は変わるだろうか？ 幸運の感触 13 問題 3. 今度はプレイヤーは 2 人だ。Bob の所持金は 51 で、Alice の所持金は 50 で あるとする。賭けはあと 2 回を残すのみ。2 回のうちの最初の賭けでは Bob が、最後の賭けでは Alice が先にどちらにいくら賭けるかを宣言する。Bob には 50% 以上の勝率があるだろうか？ その場合、具体的にどれくらいの勝 率だろうか？ 問題 4. 問題 3 と同様、Bob が 51、Alice が 50、残りの賭けは 2 回とする。今回は最 初の賭けでは Alice が先で、最後の賭けでは Bob が先に賭けをする。Bob が 1/2 以上の確率で勝てる方法はあるだろうか？ あるとしたらどれくらい？ 問題 5. 今回も前回同様の条件、つまりあと 2 回の賭けが残っていて、Bob が 51、 Alice が 50 の所持金を持ち、最初の賭けでは Alice が先に、最後の賭けでは Bob が先に賭ける。だが今回は、1 回目の賭けで Bob は 20 を賭けることを あらかじめ宣言している。ただし、表に賭けるか裏に賭けるかは、Alice が どのように賭けるかを聞いてから決める。Alice は勝率を 50% 以上にする ことができるだろうか？ バレエのオーディション、オリンピックでの勝利、狭い階層社会の中での出世など を想像してほしい。数少ない席を巡っての競争にさらに拍車がかかるにつれて、一人 がとるリスクもより大きくなってくるものだ。これにあなたが賛同するかどうか、次 の問題で見てみることにしよう。 問題 6. Bob に Alice、Rino、Juliana の 4 人がそれぞれ 100 の所持金を持っている。 賭けはあと残すところ 2 回になり、みな勝つことに躍起になっている。連 携プレイはなしだ。Bob と Alice はコインの表に 100 賭けた。Rino は裏に 100。さて、次は Juliana が賭けをする番である。このとき、最後の賭けで自 分が一番最初に賭けをしなくてならないことを、Juliana は知っている。こ れを考慮して、Juliana は今どのように勝負をするか決めなければならない。 もし、Juliana が今、表か裏のどちらかに 90 賭けたとしたら、彼女の勝率は どれくらいであろうか？ Juliana はどのように賭けたらよいのだろうか。 3 （解答は p. 95） P 14 第 I 部 マインド・ゲーム インフォメーション・ゲイン Information Gain おしゃれで人気者のゲームショーの司会者、ジェフ・ニコラスがジョーダンと彼 の 5 人の友人アリアナ、ボブ、キャロライン、デイビッド、エレン（Ariana, Bob, Caroline, David, Ellen）にコンテストに出ないかと声をかけた。彼らはみな優秀な数 学者で、パズル愛好会であるオムニヒューリストクラブのホープたちだ。 インフォメーション・ゲイン 15 「さあ、コンテストをはじめますよ。今から私は、ここにいるジョーダン君のお友 達に目隠しをして、1 から 10 の番号札のついた帽子をかぶせます（同じ番号の帽子 を複数の者がかぶる場合もあります）。そして、お友達 5 人を監視テレビモニターの ついた部屋へと案内いたします。お友達の皆さんが部屋に入ったら、私の決めた順番 で丸く並んでもらいます。そして、目隠しを外してもらいますが、反射のないレンズ でできたサングラスをつけていただきます。これによってそれぞれのお友達は、自分 以外の周りの友達の帽子に書いてある番号を見ることができます。でも、みなさんの 間でアイコンタクトなどで秘密の連絡を取り合うことはできません。」 「ジョーダン君、あなたもそして観客のみなさんも、テレビモニターで部屋の中に いるお友達と頭の上にある数字を見ることができます。ただしお友達からはあなたを 見ることはできません。また、私は 1 枚の青い切符と、1 枚の赤い切符を手に持って います。ジョーダン君、君は私にどちらか 1 枚の切符を、5 人のうちの誰かに届ける ように命ずることができます。ジョーダン君、あなたができることは、たったこれだ けです。窓ガラスを叩いたりなどして合図を送ったりすると、あなたのチームはただ ちに失格となります。」 「オムニヒューリストクラブの方々、あなた方も話をしたり、合図を送ったりする ことはできませんよ。その場合もまたチームは失格となります（当然、私は切符を届 けること以外はいたしません）。あなた方は自分の頭の上にある番号を見ることはで きませんが、自分以外の人たちの頭上にある番号は見ることはできます。また、誰が 何色のチケットを受け取ったかということも分かります。 」 「私の合図で、挑戦者たちは指で自分の番号を当ててください。もし指で表した番 号が帽子の番号と一致していれば、その挑戦者には何千ドルもの大金が渡されます。 もし全員が数を当てられたら、ジョーダン君にも 5,000 ドルの賞金が授与されます。 でも、お友達の中に一人でも不正解の方がいたら、私の勝ちです。そのときは、アル マーニのスーツを買っていただきましょう。 」 ジョーダンは驚いて聞いた。「それだけなのか？ Ariana や Bob たちは、誰が切符 をもらったのかということと、切符の色だけしか分からないのかい？」 「そのとおりです。でも、覚えていらっしゃいますかな？ お部屋の中のご友人は他 の人の帽子についてる番号は見えるんですよ。それでも、やはり難しいでしょ。私、 アルマーニのスーツいただけそうですね。 」 第 I 部 マインド・ゲーム 16 問題 1. ジョーダンと 5 人の友人は、このコンテストのルールを知った後、6 人でど のようなときに、どのカードを誰に渡すかの戦略を事前に練ることができ る。ジョーダンの友人全員が正しい番号を、確実に当てられるような戦略は 存在するだろうか？ もしあるのならば、その戦法を説明してほしい。そう でなければ、ジョーダンにはどれくらいの勝率があるのだろうか？ ウォームアップ問題 P3 問題 1 に取り組む前に、ここで少し簡単な問題を出してみる。ジョーダンが考 えるべき戦略のヒントになるだろう。もし、ジェフ・ニコラスがいつでも続き番号 の帽子をかぶせるという（例えば 4、5、6、7、8 のように）制限があったとしたら、 ジョーダンによい戦法はあるだろうか？ ウォームアップ問題の解答 ジョーダンは次のような戦略をとればよいのではないか。Ariana は 1 を、Bob は 2、Caroline は 3、David は 4、Ellen は 5 と 6、というように各人がある数字を代表 する役となる。つまり、例えばジョーダンが Ariana に切符を渡したら、数字の連続 番号は 1 から始まる、ということを部屋のみんなに伝えることを事前にチーム内で取 り決めておくのである。もし Bob だったら 2、Caroline だったら 3、David だったら 4 から始まるというように。Ellen が青い切符を受け取った場合は 5 から、切符が赤 だったら 6 から番号は始まるというプロトコルだ。これによりジョーダンは、1 から 6 までの数字の情報を部屋にいる数学者たち全員に伝えることができる。 このようにしてジョーダンが切符を渡したとき、部屋にいる数学者たちは全員、連 続する番号の最初の数を知ることができる。そして、ほかの仲間の数を見ながら消去 法で自分の頭の上にある数を割り出せばよいわけだ。番号札は 1 から 10 までである ことを思い出してほしい。 さてさて、ジェフ・ニコラスからのチャレンジでは、その番号は連続番号である必 要もないし、数字がそれぞれ異なる必要すらない。さあ、賞金を手にすることはでき るのだろうか？ 3 （解答は p. 98） P