 |
 |
|
|
|
|
|
|
刑事はいきなり本題に入った。
「ここに5人の証人がいる。しかし，誰ひとりとして，証言を完全には信用できない。彼らは10人の麻薬取引容疑者のグループを追跡していた。容疑者ひとりひとりについて，麻薬を所持しているかどうか，5人の証人に1票ずつを投じてもらった。その結果をまとめると次のようになる」。 |
|
 |
| 容疑者１： |
５票全部が「所持」 |
| 容疑者２： |
５票全部が「不所持」 |
| 容疑者３： |
３票が「不所持」，
２票が「所持」 |
| 容疑者４： |
５票全部が「所持」 |
| 容疑者５： |
４票が「所持」，
１票が「不所持」 |
| 容疑者６： |
５票全部が「不所持」 |
| 容疑者７： |
３票が「所持」，
２票が「不所持」 |
| 容疑者８： |
５票全部が「所持」 |
| 容疑者９： |
５票全部が「不所持」 |
| 容疑者10： |
４票が「不所持」，
１票が「所持」 |
|
 |
|
|
 「５人の証人が投じた総数50票のうち，９票が間違っているとしたら，どの容疑者が麻薬を所持し，どの容疑者が所持していないかわかるだろうか？しかも，証人が買収されていて，間違いの過半数が実際は麻薬を所持しているのに不所持とするものだったとしたら……」。
まず，ウォーミングアップ問題だ。「考えられる間違いの最小数はいくつだろうか？」 答え：ひとりの容疑者に対して所持，不所持に票が分かれている場合は，どちらかが間違いだ。したがって，少なくとも少数意見の票数分の間違いを含んでいる。
ここに挙げた例では，４人の容疑者について票が分かれた。３対２が２回（容疑者３と７），４対１（容疑者５と10）が２回起きている。少数意見の票数を全部足すと６になる。これが間違いの最小数だ。 |
|
 |
| |
 |
|
訳者 坂井公（さかい・こう）
筑波大学数学系助教授，理学博士。専門は理論計算機学。 |
著者 Dennis E. Shasha
ニューヨーク大学クーラント研究所教授。専門は計算機科学。 |
|
|
|
 |
|
| |
