- 642 名前：617 [2009/06/03(水) 20:31:16 ]
- こちらで用意した(ii)の答え↓
１〜1788番は何を提案しても処刑
1789番(残り8212人)の案は
1790〜5884番と1789番自身の4096人は死にたくないから無条件で賛成
5885〜10000番の中の10人に金貨を与えれば、その10人は賛成
以上4106人(ちょうど半数)の賛成により可決される
一般に、海賊の数が金貨の総数aの２倍以上の時、残りの海賊が2a+2^n 人(n=0,1,..)
で可決される(今回は残りが8212=2*10+2^13 人)
9979番(残り22人)の案は[9980番の案で１枚も貰えない11人のうち10人に１枚ずつ与える]
だから配り方は一意に定まらず、[確実に貰えない者]と[一枚貰える可能性がある者]に分かれ
全ての者に[金貨が貰えない可能性がある]ことになる
9978番(残り23人)は何を提案しても処刑
9977番(残り24人)は[9979〜10000番の中の10人に１枚ずつ与える]提案をすれば
その10人は、[金貨が貰えない可能性がある]よりも[確実に金貨が貰える]方を優先させる・・・(*)
ので賛成し、9978番と9979番自身も賛成するので可決される
このような推論をすると
1789番が金貨を与えるのは5885〜10000番の中の10人なら誰でもよいこととなる
問題の条件で(*)は成立してると思うのだが
(*)が不成立or成立してるかどうかがわからない場合は
次に可決する提案で[確実に貰えない者]に与える提案をすれば、必ず賛成してくれる
よって1789番は5885番の提案で[確実に貰えない者]↓
5885〜7932,8957〜9468,9725〜9852,9917〜9948,9965〜9972,9977,9978,
9980,9981,9983,9985,9987,9989,9991,9993,9995,9997,9999
の中の誰か10人に１枚ずつ与えればよい
|
 |
