日経サイエンス

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

CONTENTS


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

パズリングアドベンチャータイトル
難易度 ★☆☆
悪い知らせの報告法 デニス・シャシャ

 良い知らせならばともかく,悪い報告をしたいという人はいないだろう。相手が社長ならばなおさらだ。しかし,報告せずに放っておけば,事態は悪化するばかりだ。
 5人の部長,アーサー,バーナード,キャロル,ダニエル,エレンが部屋に集まり,ある知らせについて相談している。彼らのうち3人はその知らせを悪い知らせだと考え,2人はそう考えていない。それでも,その知らせとともに「少なくとも3人が悪い知らせと判断しているが,5人全員がそう考えているわけではない」と社長に報告すべきだという点では5人で一致している。これを「3以上5未満」報告と呼ぼう。彼らはまた,5人の個々人がどう判断しているかについては,社長に知られないようにしたいと考えており,この点でも意見が一致している。これを「匿名性」と呼ぶ。
 社長は彼ら1人ずつから報告を聞き,本人とその他2人以内に言及する答えを聞かないと満足しない。 これを「3言及制限」と呼ぶ。 つまり,「5人のうち3人以上はその知らせを悪い知らせと考える」といった報告では満足しない。
image
GARY ZAMCHICK
「エレン,ダニエル,私の3人のうち少なくとも2人は悪い知らせだと考える」「アーサーと私の2人のうち少なくとも1人は悪い知らせだとは考えていない」といった報告を望んでいる。報告者が別ならば,同じ2人組や3人組に対する言及でもよい。

ウォーミングアップ問題
 「匿名性」と「3言及制限」を守りながら「3以上5未満」報告を行うには,部長たちはどのように言えばよいか。

ウォーミングアップ問題の答え
 部長をそれぞれA,B,C,D,Eとイニシャルで表し,A,C,Dが悪い知らせだと考えているとする。AとBはともに「A,Bの少なくとも1人は悪い知らせだと考える」と言い,DとEはともに「C,D,Eの少なくとも2人は悪い知らせだと考える」と言い,Cは「A,B,Cの少なくとも1人は悪い知らせだとは考えていない」と言う。A,B,D,Eの報告から少なくとも3人が悪い知らせだと考えていることが保証され,最後のCの報告から悪い知らせだとは考えない部長がいることが保証される。これらの報告からは,A,Bのどちらが悪い知らせと考えているかはわからないし,C,D,Eのうちの誰が悪い知らせと考えていないのかはわからないので,匿名性が保たれる。

問1: ウォーミングアップ問題では,悪い知らせと判断しているのが3人なのか4人なのかはわからない。匿名性と3言及制限を守りながら,5人のうち3人だけが悪い知らせと判断しているという報告ができるか。できるのならば,どうすればよいか。できないのなら,その理由を答えよ。
 
問2:
同じ条件下で,4人が悪い知らせだと考えているという報告ができるか。もしそうならどうすればよいか,できないのならその理由を答えよ。
 
問3:
問題2を,4人以上(4人か5人)が悪い知らせと考えているという報告に変更するとどうなるか。

 
答えはこちらから
 

訳者 山崎秀記(やまさき・ひでき)
一橋大学商学部教授。専門は計算機科学。
 

著者 Dennis E. Shasha
ニューヨーク大学クーラント研究所教授。
専門は計算機科学。
 
原題名
Bad News Bears
(SCIENTIFIC AMERICANのウェブサイト
http://www.sciam.com/
より)
 

 
Copyright 2005 NIKKEI SCIENCE Inc., all rights reserved