リークしたのは誰だ？：日経サイエンス

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

HOME ＞パズリング・アドベンチャー＞リークしたのは誰だ？

ご購入のご案内

検索方法はこちら

サイト内検索結果に戻る

リークしたのは誰だ？

デニス･シャシャ

　ある政府機関の長官には何でも相談できる9人の顧問がいる。しかし最近，秘密の案件が彼らに話した翌日に新聞に出てしまうという事件が起こった。通常，リークした人物をつきとめるには，それぞれの容疑者に異なったおとり情報を流して，どれが漏れるかを調べるという方法をとる。しかし，今回はその方法が通用しないことがわかった。新聞の編集長は，少なくとも3人の顧問から同じ情報が取れなければ，それを新聞に載せないのだ。長官は，リークしているのが3人だけであることについては自信がある。

　長官はジレンマに陥った。もし全員に同じおとり情報を流したら，それは必ず新聞に載るだろうが，そこからは何の結果も得られない。しかし，1人か2人に流しただけでは新聞に出ない。顧問のうちから次々に3人を選んでは，それぞれに異なった情報を流せばよいのだが，9人のうちから3人を選ぶ方法は84通りもあるので，とても実現できそうにない。

　とうとう長官は次のような戦略にたどりついた。1日に1つの情報を4人にだけ教えるのだ。いろいろな4人の組み合わせを試すうちに，リークが起こったら，そこから問題の3人を絞り込むことができる。長官は2つの目標を立てた。1つは，いったんリークが起きた後はリークを2回以内に留めて犯人をつきとめること。もう1つは，最大25回のテストで確実にリークが起こるような4人の組み合わせの列を作ることだ。長官に代わってこの問題を解き，彼をサポートしてほしい。

頭のウォーミングアップ問題：長官が1日目に顧問1，2，3，4に情報を流したときは何も起こらなかった。2日目に顧問2，3，4，5に情報を流したときも何も起こらなかった。しかし，次の日に顧問1，2，4，5に流した情報は新聞にリークされたとする。どの3人が犯人だろう？　3日目の4人の中から3人を選んだときに犯人の可能性がある組み合わせは1-2-5と1-4-5だ。これ以外の3人の組み合わせが犯人ならば，3日目よりも前にリークが起こっているはずだからだ。犯人が3人しかいないとわかっているので，あと1回のテストで3人組をつきとめることができる。

　もし，おとり情報を4人に限らずもっと多くの顧問に流してもよく，いったんリークが起こった後で，さらに3回以上のリークが我慢できるならば，最大25回よりもずっと少ないテストで問題の3人組を発見できても不思議ではない。読者の皆さんはどう思われるだろうか？

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

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

	Dennis E. Shasha

	ニューヨーク大学クーラント研究所教授。専門は計算機科学。原題名 Plumbers （SCIENTIFIC AMERICAN December 2002）


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