日経サイエンス

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

CONTENTS


メールニュース会員登録(無料)
モバイルマガジンのご案内
定期購読のご案内
SCIENTIFIC AMERICAN
バックナンバーのPDF販売

パズリングアドベンチャータイトル
難易度2
秘密は皆で分けて持とう デニス・シャシャ

 メッセージはどんなものでも1つの数値として表現することができる。たとえば,「Let's meet at the corner of Constitution and Lake」という文中の「meet」という語は,大多数のコンピューターの中では,ASCIIという名で知られるコードによって,10進数の109 101 101 116 として表されている。
 今月の問題は秘密の指示をいかに安全に送るかだ。待ち合わせの場所と時間といったメッセージを,5人の密使を使って送りたい。しかし,密使のうち1人か2人は敵に捕まる恐れがある。だから,メッセージ情報を分割して密使たち全員に持たせ,いずれか3人が集まれば元のメッセージを復元できるが,2人以下では復元できないようにしたい。
 メッセージは数値としてコード化されているので,これは1つの数値の情報を5人にばらして持たせる問題として捉えることができる。直感的には,それぞれの密使にその数値の一部を持たせるのがいいと思うだろうが,それはさほど安全な方法とはいえない。密使が2人いても何ら有効な情報は得られず,3人いれば完全なメッセージが得られるようにしたい。2人と3人との間に情報の「断崖」を構築したいのだ。これにはもっと巧妙な仕組みを工夫する必要がある。

ウォーミングアップ問題
 まずはウォーミングアップ問題を考えよう。xy座標平面上の1点,たとえば(13,6)に宝を隠し,その場所を示す情報を3人の友人に分けて伝えておくという場合を考えよう。3人のうちどの2人が集まっても,宝の位置がわかるが,1人だけではわからないようにしたい。
 それには手がかりとしてマーサにはたとえばx=13という直線を教えておく。そして,ジェイムにはy=6,バレリアにはy=x−7を教えておくといい(下図)。このとき,友人たちは,宝を見つけるためにこれらの情報をどう使えばいいだろうか。読者の皆さんは,宝を見つけるのには2人が必要でかつ十分なことがわかるだろうか(答えは下に示してある)。 
 同様な考え方をすれば密使を5人にした場合の問題にも解が得られる。

image

ウォーミングアップ問題の答え
宝は教えられた直線の上のどこかにあるが,直線上には無限の点があるので,1人だけでは,誰も宝の位置を示す確たる情報を得られない。しかし2人いれば,2本の直線の交点として,宝の位置が決定できる。1人の情報だけでは,無限の不確実性に直面していたのだが,もう1人の情報が加わることで正確な知識に変わるのだ。
image

 
答えはこちらから
 

訳者 坂井公(さかい・こう)
筑波大学数学系助教授。
専門は計算機科学。
 

著者 Dennis E. Shasha
ニューヨーク大学クーラント研究所教授。
専門は計算機科学。
 
原題名
All or Nothing
(SCIENTIFIC AMERICAN February 2004)
 

 
Copyright 2005 NIKKEI SCIENCE Inc., all rights reserved