双子の冒険 (2) 信用できない目撃者：日経サイエンス

	日経サイエンスは米国の科学雑誌「SCIENTIFIC AMERICAN」の日本版です。
	HOME

HOME ＞パズリング・アドベンチャー＞双子の冒険 (2) 信用できない目撃者

ご購入のご案内

検索方法はこちら

サイト内検索結果に戻る

双子の冒険 (2) 信用できない目撃者

デニス・シャシャ

算数程度の知識とひらめきがあれば解けます。ぜひ，挑戦を！
　
　クロエがラクロスの試合から帰宅すると，すぐに電話が鳴った。「オヘンリー巡査から呼び出しがかかった。信用できない目撃者がいるんだってさ」。双子の弟エリからの連絡だった。
　オヘンリー巡査は難事件に出くわすと，しばしば数学的センスに恵まれたこの12歳の双子の姉弟に助けを求めてくる。彼は２人に状況を説明するのに，あるパズルの歴史から話を始めた。
　「常に本当のことを言う人と，常に嘘をつく人が出てくる古典的なパズルがあるだろう」とオヘンリー巡査は話す。「彼らにいくつかの質問をして，どちらが嘘つきなのかを見分けたり，嘘つきがわからないままでも，ある事実を見つけるという問題だ」。
　「たとえば，古典的な嘘つきパズルの女王級の問題はこういうものだ。初めての土地で一本道をたどって歩いているとしよう。すると，道が２つに分かれた地点にさしかかり，そこを１人の兵士が警護している。ここから一方の道を進むと，平和的な人々の住む正直村に達し，食べ物を分けてもらえる。そこの村民は常に本当のことを言う。しかし，もう一方の道を進むと，常に嘘を言う人々が住む嘘つき村に着いて，殺されてしまうのだ。
　分かれ道に立つ兵士は，どちらか一方の村から派遣されているが，外見では判断できない。きみたちは，この兵士に“はい・いいえ”で答える質問を１つだけすることができ，その答えをもとに自分の運命を決めなくてはならない」。

ウォーミングアップ問題

　どんな質問をしたらいいだろう？

ウォーミングアップ問題の答え

　一方の道を指しながら，「この道はあなたの村に通じていますか？」と聞く。理由：まず，嘘つき村に通じる道を指していたとしよう。すると，兵士が嘘つきであってもなくても，答えは「いいえ」となる。また，正直村に通じる道を指していたとすると，兵士は必ず「はい」と答える。兵士が嘘つきか正直者かはわからないが，いずれにせよ，望みの村に行くことはできる。

GARY ZAMCHICK

　オヘンリーは続けた。「ただ，現実にはこんなことはあり得ない。嘘つきといっても，いつも嘘ばかり言うわけではなく，気まぐれに本当のことを言うこともある。こうなると厄介だ。さっきの問題の兵士が気まぐれな嘘つきだったとしたら，彼は自分の村に通じる道を教えるかもしれない。
　いま，兵士の一団がいて，１人だけが気まぐれな嘘つきで，残りは常に正直だとしよう。その場合は少なくとも３人の兵士にこれと同じ質問をすればよい。結果は多数決で決められる。
　私が困っているのはある犯罪に関することなんだ。捜査上の秘密だから，詳しいことを話すわけにはいかない。今のパズルにたとえて説明しよう。
　中が見えない箱の中に，ある物が１つ入っている。サイズは大か小，色は赤か緑，種類は靴か靴下だ。中の物を実際に見た人の証言を聞いて，箱に入っているものを当ててほしい。中を見た人は３人いるが，その中に気まぐれな嘘つきが１人交じっている可能性がある。残りの２人は正直だ」。

問１：はい・いいえで答えられる質問を１人当たり最大３回，合計で７回まですることができる（３人に３回はできない）。物体の大きさ・色・種類を特定できるだろうか？

　「次はもっと難問だ。箱の中を見た人は６人いる。その中に気まぐれな嘘つきが２人交じっている可能性がある。残りの人は正直だ」。

問２：はい・いいえ質問を１人最大２回できるとするなら，物体の大きさ・色・種類を特定できるだろうか？

問３：靴下には緑しかなく，靴には大きなサイズしかないとすれば，質問をどこまで簡単にできるだろう？

	田中裕一（たなか・ゆういち）

	アルティス・リサーチ代表。専門は計算機科学。

	Dennis E. Shasha

	ニューヨーク大学クーラント研究所教授。専門は計算機科学。　原題名 Lying Socks （SCIENTIFIC AMERICANのウェブサイト http://www.sciam.com/より）


会社案内　\| 「日経サイエンス」はこんな雑誌　\|　個人情報の取り扱いについて　\|	Copyright 2005 NIKKEI SCIENCE Inc., all rights reserved