10分間の盗聴：日経サイエンス

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

HOME ＞パズリング・アドベンチャー＞ 10分間の盗聴

ご購入のご案内

検索方法はこちら

サイト内検索結果に戻る

10分間の盗聴

デニス･シャシャ

　あなたは政府の情報部員で，本部に送るべき秘密のメッセージをいくつか持っているとしよう。ところが，敵のスパイがそのメッセージを傍受しようと狙っている。あなたのマイクロ波通信を盗聴するには，発信機の視界の中にいなければならず，そのような場所にいるのはスパイにとって，捕まる危険を冒すことになる。だから，スパイが盗聴を試みるのは一度きりで，せいぜい10分間ということは確実だ。

　問題なのはスパイがどの10分間に盗聴を試みるか，あなたにはわからないということだ。

　送るべきメッセージはAからGまで合計7つあり，一刻も早く全部を送ってしまいたい。それぞれのメッセージの伝送には次の時間がかかる。

A：	B：	C：	D：	E：	F：	G：
2分	3分	4分	5分	6分	7分	8分

　これらのメッセージのうち3つまでなら，スパイに傍受されても大丈夫だ。また，1つのメッセージは一部分を聞いても敵の役には立たないので，傍受されたといえるのは最初から最後まで全体を盗聴された場合だ。

　各メッセージは，送り始めたら同じ通信機から最後まで送り続けなければならないが，何台でも好きなだけ通信機を使って，同時並行的に複数のメッセージを送ることができる。複数を同時に送り始めてもいいし，1つを送っている途中に他のものを送り始めてもいい。ただし，各メッセージの送信は分単位でちょうどの時刻にのみ送信開始が許される。例えば時刻4分00秒にならば送信できるが，4分01秒に送信を始めることはできない。

| ウォーミングアップ

　ウォーミングアップとして，敵のスパイに全体を盗聴されてもかまわないメッセージ数がただ1つの場合を考えよう。通信に要する全時間を最短にするためには，各メッセージをいつ送り始めるのがいいだろうか。36分の解を下に示す。

　今月の問題の場合，3つまでならメッセージが傍受されても仕方ないとするので，通信時間をかなり減らすことができる。7つのメッセージを15分以下で送る方法があるだろうか。これらの7つに加えて，4分のメッセージをさらに3つ送らねばならない場合，全部で10個のメッセージ中，傍受されるのを3個以内にとどめ，かつ20分以内で全メッセージを送ることができるだろうか。

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

　傍受されるメッセージをせいぜい1個までにとどめて，全メッセージを36分間で送るには，メッセージBを時刻0分に送り始め，以下Fを4分，Dを10分，Gを13分，Cを20分，Eを25分，Aを34分に送り始めるといい。どの10分間をとってみても，メッセージの全体を2つ以上含むことはない。全通信時間をもっと短くできるだろうか？

※画像をクリックしていただくと、大きな画像でご覧いただけます。

	坂井公（さかい・こう）

	筑波大学数学系助教授，理学博士。専門は計算機科学。

	Dennis E. Shasha

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


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