筋道で絞る、見切って選ぶ

手がかりから、ただ1つの答えを絞り出す。あるいは、情報が足りないまま、どこかで決める。ここの3つの作品は、「考えて決める」遊びです。

手がかりの表（このサイトの「ロジックグリッド」）

「Aさんは赤い家の人ではない」「猫を飼っている人は、青い家のとなり」のような手がかりを読んで、表を埋めて、全員の組み合わせを決めます。 プログラムで、36問のすべてが解をちょうど1つだけ持つことを確かめました。さらに、どの問題も、手がかりと「同じ行に1つだけ」という線引きの推理だけで解けます。あてずっぽうは要りません（logic-grid/engine.test.ts）。

この種のパズルで有名なのが「アインシュタインの謎」とも呼ばれるものです。ただし、アインシュタインが作った、という話に根拠はありません。ルイス・キャロルの作という説も同じです。 確かなところでは、この形のパズルは、1962年12月17日号の雑誌に載り、解答は1963年3月25日号に載ったことがわかっています。

騎士と悪党（このサイトの「騎士と悪党」）

島には、いつも本当のことを言う「騎士」と、いつもうそを言う「悪党」がいます。3人がそれぞれ何かを言います。誰が騎士で、誰が悪党でしょうか。 3人の組み合わせは、騎士か悪党かで 2×2×2＝8 通りです。1つずつ、その言葉と矛盾しないかを調べていけば、必ず答えが出ます。 プログラムで、68問のすべてが、8通りのうちちょうど1つだけが矛盾しないことを確かめました。どの問題も3人が話し、言葉は少なくとも2種類の型を含みます（knights-knaves/engine.test.ts）。

「騎士と悪党」という名前を広めたのは、レイモンド・スマリヤンの1978年の本です。似たパズルはそれより前にもあり、1953年のクライチックの本や、1931年にネルソン・グッドマンが新聞に載せたものが知られています。 根っこには「うそつきのパラドックス」があります。「私はうそつきだ」と言う人が、本当のことを言っていても、うそを言っていても、矛盾してしまう話です。

見切って選ぶ（このサイトの「秘書問題」）

応募者が1人ずつ来て、その場で採用か不採用かを決めます。断った人は、二度と呼べません。いちばんいい人を選ぶには、どうすればよいでしょうか。 最適な作戦は、最初の約 n/e 人（e は約2.718）を見送って、その後は、それまでの誰よりもよい人が来たら、すぐ選ぶ、というものです。人数が多いと、成功する確率は 1/e ≒ 0.368 に近づきます。「37%ルール」と呼ばれることもあります。

プログラムで、人数が20人のとき、最適な見送り人数は7人で、成功率は約0.384であることを確かめました。人数が大きいときは、1/e に近づくことも確かめました。 また、見送りの人数ごとの成功率の式が、順番を全部ためした結果と、7人までの場合に一致することも確かめています（secretary-problem/engine.test.ts）。

歴史では、メリル・フラッドが1949年ごろ「婚約者問題」として話したが、発表はされなかった、とされています。活字になった最初は、マーティン・ガードナーの1960年2月号のコラムです。 リンドリーの1961年の論文など、解いた人は何人かいて、「最初に解いたのは誰か」には論争があります（ファーガソンの1989年の論文が、その議論を扱っています）。ここでは決めません。

共通すること

• 矛盾を見つける：手がかりと合わない組み合わせを、1つずつ消していきます。
• 答えが1つだと確かめる：よいパズルは、答えがちょうど1つです。
• 選べなくなる前に決める：秘書問題は、情報が足りなくても、ルールに従って決める練習です。

3つとも、問題はこのサイトで作ったものです。「アインシュタインの謎」そのものは載せていません。