日経サイエンス

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

CONTENTS


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

パズリングアドベンチャー 問題
仲介人のふりをした盗人を探せ!  
  デニス・シャシャ 難易度 ★☆☆

image

アリスはボブ宛てにダイヤモンドの原石を封筒に入れて送る。封筒は5人の仲介人のうち,送り手のアリスが選んだ3人の手を経てボブに渡る。仲介人をM1,M2,M3,M4,M5としよう。ボブと5人の仲介人はそれぞれ自分専用の私書箱のような金庫を持っていて,封筒の受け渡しはこの金庫式私書箱を通して行われる。ある人の金庫に封筒が入れられると,金庫の持ち主は誰にも見張られていないことを確認した上で金庫を開け,封筒を取り出す。金庫を開けられるのは本人だけだ。
封筒がボブの手もとに届くと,ボブはすべてのダイヤモンドが到着したかどうかをアリスに告げる。ボブとアリスは完全に信頼しあっており,2人は常に真実を告げると考えてよい。

ウォーミングアップ問題:

仲介人のなかに盗人がいるというウワサがある。盗人は1人だけらしいが,盗人などいないという説もある。盗人の手に封筒が渡れば,必ず盗みが行われる。貴重なダイヤモンドの原石を送る前に見た目の似たただの石ころをボブに送って,5人の仲介人のうち盗人がいるとすれば誰であるのかを突き止めたい。3回以下の送付で盗人が(もしいるとすれば)誰なのかを特定するには,各回の送付で仲介人をどのように選べばよいか。


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

1回目はM1 M2 M3を仲介して送る。盗みがあれば2回目はM3 M4 M5を仲介して送る。
盗みがあれば(共通する)M3が盗人。
なければ(M1かM2が盗人なので),3回目はM1 M4 M5を仲介して送る。
盗みがあればM1が盗人だ。なければM2が盗人だ。
なければ(盗人がいればM4かM5なので)2回目はM1 M2 M4を試す。
盗みがあればM4が盗人だ。なければ3回目はM1 M2 M5を試す。
盗みがあればM5が盗人で,なければ盗人はいない。

 

問題1:

ウォーミングアップ問題と同様に,5人の仲介人がいて,そのうちの3人を選ぶことができる。また盗人は機会があれば必ず盗みをはたらく。今度は盗人が2人以下だとする。すべての盗人を確定するには最少で何回の送付が必要か。


次の問題は私にもまだ解けていない。

問題2:

封筒は発送元で封印され,ダイヤモンドを盗むには封印を破らなければならない。しかし,盗みがあっても封筒は必ず配達される。さらに,封筒の表には,各仲介人がよい状態で届いたか否か鉛筆で記入する。ただし盗人だけは嘘を記入することができるし,以前に書かれたものを書き換えることもできる(嘘をついたり書き換えたりは,しなくてもよい)。この場合,盗人を特定するのに何回の送付が必要か。

答えはこちら
■訳者 山崎秀記(やまさき・ひでき)
一橋大学商学部教授。専門は計算機科学。
■著者 Dennis E. Shasha
ニューヨーク大学クーラント研究所教授。専門は計算機科学。
原題名
Dangers in Transit
(SCIENTIFIC AMERICANのウェブサイト http://www.sciam.com/より)

 
Copyright 2006 NIKKEI SCIENCE Inc., all rights reserved