安心したい独裁者：日経サイエンス

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

HOME ＞パズリング・アドベンチャー＞安心したい独裁者

ご購入のご案内

検索方法はこちら

サイト内検索結果に戻る

安心したい独裁者

デニス・シャシャ

GARY ZAMCHICK

　有史以来，独裁者はジレンマにとらわれてきた。つねに護衛が必要だが，護衛兵に裏切られるかもしれない。部屋の中に自分に忠実な護衛兵より裏切り者の方が多くいたら，襲われてしまうだろう。
　ある国の独裁者には７人の護衛兵がいた。ある日，彼は勇気を出して，護衛兵全員を自分の部屋に集めてみた。そのとき，反乱は起きなかったので，護衛兵の半数以上は忠実だとわかった。問題は，護衛兵といえども休みが必要なことだ。護衛兵の労働時間は一日に合計16時間までとされていて，８時間は休ませなくてはならない。
　護衛兵をグループに分け，各グループで忠実な護衛兵が２人以上いて，かつグループの過半数であるようにしたい。そのようなグループを「信頼できるグループ」と呼ぼう。問題はどうグループ分けをすればよいかだ。独裁者はお抱えの数学者Mに助けを求めた。
　Mは召されるとお辞儀をして言った。「閣下，護衛兵たちにお尋ねになればよろしいと存じます。彼らは裏切り者を知っているでしょう」
　「そうじゃ。しかし，どの告発を信じてよいかがわからぬ」
　「閣下の判断は賢明です」。Mは言った。「しかし，告発からわかることもあります。忠実な護衛兵は真実を告げますが，そうでないものが言うことは真実かもしれないし嘘かもしれません。必要な結論は閣下，すべての告発において告発者か告発された者のどちらかは忠実でないということです。忠実でない護衛兵による告発では，両者が忠実でないということもあります」。

ウォーミングアップ問題

護衛兵が５人で，その告発が下図のようだとしよう。ここで，矢印による表記「A→B」は護衛兵Aが護衛兵Bのことを忠実でないと告発したことを意味する。過半数の３人は忠実だと仮定すると，忠実なのは誰か。

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

CとEは忠実で，A，Dのうちの１人は忠実である。なぜか。A，B，Dの間にはすべて（どちらかの向きの）矢印があるから，そのうち２人は忠実でない。忠実でないのは２人だから，残りのCとEは忠実だ。忠実なCを告発しているBは忠実でない。この図からは，AとDのどちらが忠実かまではわからない。

問１：右の告発図をもとに，この５人の護衛兵で，独裁者がつねに「信頼できるグループ」に護衛されるようなスケジュールを立てよ。

問２：７人の護衛兵での告発図が右のようになったとしよう。独裁者がつねに「信頼できるグループ」に護衛されるようにできるか。

問３：７人の護衛兵の間の告発図で，矢印の最大本数は何本か。ただし，その過半数は忠実だとする。また，AがBを告発する場合と，BがAを告発する場合は別にカウントする。

	山崎秀記（やまさき・ひでき）

	一橋大学商学部教授。専門は計算機科学。

	Dennis E. Shasha

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


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