しいたげられたしいたけ

空気を読まない。他人に空気を読むことを要求しない

「海賊と金貨」のパズル(基本形)

備忘的に 08/30 にメモだけ書いた内容だけど、自分なりにまとめておこう。多分全3回の第1回。
(1)5人の海賊が、100枚の金貨を分配する。
(2)海賊にはボス以下腕力の差によって序列がある。
(3)まずボスが分け方を提案し全員で投票する。
(4)もし賛成が半数に達しなければボスは処刑され、二番目に腕力のある海賊がボスになる。
(ボスがいくら腕力が強くても、過半数が束になったら敵わない)
(5)海賊はみんな合理的で、みんな一枚でも多くの金貨を欲しがっており、みんな処刑されたくない。
「全員に20枚ずつ平等に」というのは正解ではない。
「平等に分配するのであれば、反対票を投じてボスを処刑してしまえば、自分の分け前が増える」というのが理由なんだそうだ。
正解は数学的帰納法で考えていくのだそうだ。
人数をnとし海賊をP1、P2、…Pnと呼ぶ。
腕力はP1>P2>…>Pnであるとする。

人数n=1の場合

P1が100枚全部を総取りにすればよい。
結論はP1=100。

人数n=2の場合

P1が100枚全部を総取りにすればよい。
P2は反対票を投票するがP1自身が賛成票を投じるので、1対1で賛成が半数、P1>P2という腕力の差により可決される。
結論はP1=100、P2=0。

人数n=3の場合

P1が100枚全部を総取りにすることはできない。なぜならP2とP3が反対票を投じるのでP1は殺されてしまう。
ではどうするか?P3の立場で考える。
もし自分(P1)が処刑されたら、「人数n=2の場合」と同じになり、P2が100枚を総取りにするのでP3は1枚ももらえない。
そこで自分(P1)に99枚、P2に0枚、P3に1枚という分配を提案する。
P2は反対するがP3は「もらえないよりマシ」と思って賛成するだろう。
よってこの分配案は2対1で可決される。
結論はP1=99、P2=0、P3=1。

人数n=4の場合

増えたP4には0枚でいい。あとは「人数n=3の場合」と同じ自分(P1)に99枚、P2に0枚、P3に1枚という分配で、自分とP3の賛成票が期待できる。
なぜならP3は、次のように考える。もし自分が反対したら、一枚ももらえないP2とP4も当然反対票を投じるであろうから、P1は処刑される。するとP2をボスとする「人数n=3の場合」と同じになり、新ボスP2に99枚、自分(P3)に0枚、P4に1枚という分配になる。だから現ボスP1の分配案に賛成するしかない。
結論はP1=99、P2=0、P3=1、P4=0。

人数n=5の場合

今度は増えたP5には1枚やらなければならない。あとは「人数n=4の場合」と同じ自分(P1)に99枚、P2に0枚、P3に1枚、P4に0枚。
P3とP5は考えるであろう。もし自分たちのうち、どちらか一人でも反対票を投じたらどうなるか?P2とP4は当然、反対票であるので、ボスP1は処刑される。次はP2を新ボスとする「人数n=4の場合」と同じになり、P4が1枚もらい、自分たち(P3とP5)は1枚ももらえなくなる。だから現ボスP1に賛成せざるをえない。
結論はP1=98、P2=0、P3=1、P4=0、P5=1。
(この項つづく)