海賊の山分け

海賊の山分け
5人の海賊が100枚のコインを山分けすることになりました。
この5人には地位があり地位が一番高い人が親分となります。
親分が分配方法を提案し、親分を含む全員で賛成か反対かを投票をします。
賛成票が半数以上ならその分配方法に決まり、賛成票が半数未満なら親分は殺され残った海賊で分配をやり直します。
この5人は合理的な判断をするとき、親分が少しでも多くコインを貰うにはどのような配分方法を提案すればいいでしょうか?
海賊の人数を\(n\)とする。
配分方法は地位の高い人から順番に丸括弧の中に1位の海賊(親分)、2位の海賊(子分)、3位の海賊(子分)、…と表すとする。

\(n=1\)のとき

親分が全てのコインを貰えるので
配分は\(\left(100\right)\)となり賛成1、反対0となる。

\(n=2\)のとき

親分1人が賛成すれば可決するので
配分は\(\left(100,0\right)\)で賛成1、反対1となり可決

\(n=3\)のとき

2位の海賊は否決されれば100枚のコインを貰えるので、101枚以上コインを渡さないと賛成してもらえない。
3位の海賊は否決されればコインを貰えないので、0枚より多くのコインを渡せば賛成してもらえる。
親分は賛成するので、残り1人に賛成してもらえればよい。
これより、3位の海賊に賛成してもらえればいい。
配分は\(\left(99,0,1\right)\)で賛成2、反対1となり可決。

\(n=4\)のとき

2位の海賊は否決されれば99枚のコインを貰えるので、99枚より多くのコインを渡さないと賛成してもらえない。
3位の海賊は否決されればコインを貰えないので、0枚より多くのコインを渡せば賛成してもらえる。
4位の海賊は否決されれば1枚のコインを貰えるので、2枚より多くのコインを渡せば賛成してもらえる。
親分は賛成するので、残り1人に賛成してもらえればよい。
これより、3位の海賊に賛成してもらえればいい。
配分は\(\left(99,0,1,0\right)\)で賛成2、反対2となり可決。

\(n=5\)のとき

2位の海賊は否決されれば99枚のコインを貰えるので、99枚より多くのコインを渡さないと賛成してもらえない。
3位と5位の海賊は否決されればコインを貰えないので、0枚より多くのコインを渡せば賛成してもらえる。
4位の海賊は否決されれば1枚のコインを貰えるので、2枚より多くのコインを渡せば賛成してもらえる。
親分は賛成するので、残り2人に賛成してもらえればよい。
これより、3位と5位の海賊に賛成してもらえればいい。
配分は\(\left(98,0,1,0,1\right)\)で賛成3、反対2となり可決。

補足

\(1\leq n\leq200\)のとき(201までできる)
\(0,1\)が3回繰り返すときは\(\left(0,1\right)*3=0,1,0,1,0,1\)と表すとする。
\(n\)が奇数のとき、
配分は、
\[ \left(\frac{201-n}{2},\left(0,1\right)*\frac{n-1}{2}\right) \] となり、賛成\(\frac{n+1}{2}\)、反対\(\frac{n-1}{2}\)となる。
\(n\)が偶数のとき、
配分は、
\[ \left(\frac{202-n}{2},\left(0,1\right)*\frac{n-2}{2},0\right) \] となり、賛成\(\frac{n}{2}\)、反対\(\frac{n}{2}\)となる。

\(201\leq n\)で考える

このとき賛成でも反対でもないときは浮動票となりどちらに投票するかわからないとする。
またコインを貰うより自分の命を大切にするとする。
\(n=201\)以降を考えるために1つ前の\(n=200\)から考える。

\(n=200\)のとき

配分は\(\left(1,\left(0,1\right)*99,0\right)=\left(\left(1,0\right)*100\right)\)で賛成100,反対100で可決。

\(n=201\)のとき

奇数位の子分100人は否決されるとコインが貰えないので、0枚より多くのコインを渡せば賛成してもらえる。
偶数位の子分100人は否決されるとコインを1枚貰えるので、1枚より多くのコインを渡せば賛成してもらえる。
親分は賛成するので残り100人に賛成してもらえればいい。
これより、奇数位の子分100人に1枚を渡して賛成して貰えればいい。
配分は\(\left(0,\left(0,1\right)*100\right)\)で賛成101、反対100となり可決。

\(n=202\)のとき

2位と奇数位の子分100人は否決されるとコインが貰えないので、1枚以上で賛成、0枚で浮動票。
4位以降の偶数位の子分100人は否決されるとコインを1枚貰えるので、2枚で賛成、1枚で浮動票、0枚で反対。
親分は賛成するので残り100人に賛成してもらえればいい。
2位と奇数位の子分(100人)の中から100人にコイン1枚を渡せば100人に賛成して貰え、残った1人は浮動票になる。
これより、配分は\(\left(0,?,\left(?,0\right)*100\right)\)で賛成101、反対100、浮動票1となり可決。
ここで\(?\)記号は今あるコイン100枚を\(?\)の中から100人を選んで100枚を配るということである。
否決時コイン0枚の人にコインを上げるより否決時コイン?枚の人に優先してコインを渡すほうが得をする。
何故なら否決時コイン0枚の子分はコインを1枚以上で賛成でコイン0枚で浮動票であるが、否決時コイン?枚の子分はコインを1枚以上で賛成でコイン0枚で反対になる。
これより、否決時コイン?枚の子分にコインを1枚渡して賛成してもらい、否決時コイン0枚の子分を浮動票にするほうが得するからである。
またこれ以降はコインが足りてない状態となりコイン?枚の子分は常に101人でありその子分に変更はない。
更にこれ以降は否決時コイン0の人は常にコイン0枚であるが、親分になり否決されるのを防ぐため\(\times\)になることがあります。

\(n=203\)のとき

2位と5位以降の奇数位の子分(100人)は否決されるとコインが貰えないので、1枚以上で賛成、0枚で浮動票。
3位と4位以降の偶数位の子分(100人)は否決されるとコインを1枚貰えるかもしれないので、1枚以上で賛成、0枚で反対。
親分は賛成するので残り101人に賛成してもらえればいい。
3位と4位以降の偶数位の子分の合計101人の中から100人にコイン1枚を渡せば100人に賛成して貰え、残った1人は反対票になる。
2位と5位以降の奇数位の子分の合計101人は浮動票となる。
これより、配分は\(\left(0,0,?,\left(?,0\right)*100\right)\)で賛成101、反対1、浮動票101となり否決の可能性がある。

\(n=204\)のとき

まず2位の子分は今回否決されると親分になり否決される可能性があるので必ず賛成する。
3位と6位以降の偶数位の子分(100人)は否決されるとコインが貰えないので、1枚以上で賛成、0枚で浮動票。
4位と5位以降の奇数位の子分(100人)は否決されるとコインを1枚貰えるかもしれないので、1枚以上で賛成、0枚で反対。
親分と2位は賛成するので残り100人に賛成してもらえればいい。
4位と5位以降の奇数位の子分の合計101人の中から100人にコイン1枚を渡せば100人に賛成して貰え、残った1人は反対票になる。
3位と6位以降の偶数位の子分の合計101人はコイン0枚で浮動票となる。
これより、配分は\(\left(0,\times,0,?,\left(?,0\right)*100\right)\)で賛成102,反対1,浮動票101となり可決される。
分かりやすくするために、否決をされると次回以降に親分になり否決される可能性がある子分は\(\times\)で表す。
この\(\times\)には渡すコインは0枚でいい。

\(n=205\)のとき

2位から4位と7位以降の奇数位の子分(100人)は否決されるとコインが貰えないので、1枚以上で賛成、0枚で浮動票。
5位と6位以降の偶数位の子分(100人)は否決されるとコインを1枚貰えるかもしれないので、1枚以上で賛成、0枚で反対。
親分は賛成するので残り102人に賛成してもらえればいい。
5位と6位以降の偶数位の子分の合計101人の中から100人にコイン1枚を渡せば100人に賛成して貰え、残った1人は反対票になる。
2位から4位と7位以降の奇数位の子分の合計103人はコイン0枚で不動票となる。
これより、配分は\(\left(0,0,0,0,?,\left(?,0\right)*100\right)\)で賛成101,反対1,浮動票103となり否決の可能性がある。

\(n=206\)のとき

2位の子分は今回否決されると親分になり否決される可能性があるので必ず賛成する。
3位から5位と8位以降の偶数位の子分(100人)は否決されるとコインが貰えないので、1枚以上で賛成、0枚で浮動票。
6位と7位以降の奇数位の子分(100人)は否決されるとコインを1枚貰えるかもしれないので、1枚以上で賛成、0枚で反対。
親分と2位は賛成するので残り101人に賛成してもらえればいい。
6位と7位以降の奇数位の子分の合計101人の中から100人にコイン1枚を渡せば100人に賛成して貰え、残った1人は反対票になる。
3位から5位と8位以降の偶数位の子分の合計103人はコイン0枚で不動票となる。
これより、配分は\(\left(0,\times,0,0,0,?,\left(?,0\right)*100\right)\)で賛成102,反対1,浮動票103となり否決の可能性がある。

\(n=207\)のとき

配分は\(\left(0,\times,\times,0,0,0,?,\left(?,0\right)*100\right)\)で賛成103,反対1,浮動票103となり否決の可能性がある。

\(n=208\)のとき

配分は\(\left(0,\times,\times,\times,0,0,0,?,\left(?,0\right)*100\right)\)で賛成104,反対1,浮動票103となり可決される。

\(n=209\)のとき

配分は\(\left(0,0,0,0,0,0,0,0,?,\left(?,0\right)*100\right)\)で賛成101,反対1,浮動票107となり否決の可能性がある。

\(n=210\)のとき

配分は\(\left(0,\times,0,0,0,0,0,0,0,?,\left(?,0\right)*100\right)\)で賛成102,反対1,浮動票107となり否決の可能性がある。


\(n=215\)のとき

配分は\(\left(0,\left(\times\right)*6,\left(0\right)*7,?,\left(?,0\right)*100\right)\)で賛成107,反対1,浮動票107となり否決の可能性がある。

\(n=216\)のとき

配分は\(\left(0,\left(\times\right)*7,\left(0\right)*7,?,\left(?,0\right)*100\right)\)で賛成108,反対1,浮動票107となり可決される。

\(n=217\)のとき

配分は\(\left(0,\left(0\right)*15,?,\left(?,0\right)*100\right)\)で賛成101,反対1,浮動票115となり否決の可能性がある。

\(n=218\)のとき

配分は\(\left(0,\times,\left(0\right)*15,?,\left(?,0\right)*100\right)\)で賛成102,反対1,浮動票115となり否決の可能性がある。


\(n=231\)のとき

配分は\(\left(0,\left(\times\right)*14,\left(0\right)*15,?,\left(?,0\right)*100\right)\)で賛成115,反対1,浮動票115となり否決の可能性がある。

\(n=232\)のとき

配分は\(\left(0,\left(\times\right)*15,\left(0\right)*15,?,\left(?,0\right)*100\right)\)で賛成116,反対1,浮動票115となり可決される。

\(n=233\)のとき

配分は\(\left(0,\left(0\right)*31,?,\left(?,0\right)*100\right)\)で賛成101,反対1,浮動票131となり否決の可能性がある。


このように続き配分方法は
\begin{align*} & \left(0,\left(\times\right)*\left(n-202-\left(2^{\left\lfloor \log_{2}\left(n-201\right)\right\rfloor }-1\right)\right),\left(0\right)*\left(2^{\left\lfloor \log_{2}\left(n-201\right)\right\rfloor }-1\right),?,\left(?,0\right)*100\right)\\ = & \left(0,\left(\times\right)*\left(n-201-2^{\left\lfloor \log_{2}\left(n-201\right)\right\rfloor }\right),\left(0\right)*\left(2^{\left\lfloor \log_{2}\left(n-201\right)\right\rfloor }-1\right),?,\left(?,0\right)*100\right) \end{align*} で賛成は親分と\(\times\)と\(?\)の中から100人となり合計は、
\begin{align*} & 1+\left(n-201-2^{\left\lfloor \log_{2}\left(n-201\right)\right\rfloor }\right)+100\\ = & n-2^{\left\lfloor \log_{2}\left(n-201\right)\right\rfloor }-100 \end{align*} 反対は\(?\)でコインが0枚の1人で浮動票は配分が0となる子分
\begin{align*} & 2^{\left\lfloor \log_{2}\left(n-201\right)\right\rfloor }-1+100\\ = & 2^{\left\lfloor \log_{2}\left(n-201\right)\right\rfloor }+99 \end{align*} となる。
必ず可決されるには反対票と浮動票の合計が賛成票以下であればいいので、
\[ n-2^{\left\lfloor \log_{2}\left(n-201\right)\right\rfloor }-100\geq1+2^{\left\lfloor \log_{2}\left(n-201\right)\right\rfloor }+99 \] となり移項すれば、
\[ \frac{n}{2}-100\geq2^{\left\lfloor \log_{2}\left(n-201\right)\right\rfloor } \] 対数をとって、
\[ \log_{2}\left(\frac{n}{2}-100\right)\geq\left\lfloor \log_{2}\left(n-201\right)\right\rfloor \] \(202\leq n\)なので、\(n=201+m,m\in\mathbb{N}\)とおくと、
\begin{align*} \log_{2}\frac{m+1}{2} & \geq\left\lfloor \log_{2}\left(m\right)\right\rfloor \end{align*} となるので、
\[ \log_{2}\left(m+1\right)-1\geq\left\lfloor \log_{2}\left(m\right)\right\rfloor \] となる。
ここで、任意の\(m\in\mathbb{N}\)はある\(k\in\mathbb{N}_{0},j\in\left\{ 0,1,\cdots,2^{k}-1\right\} \)が存在し、\(m=2^{k}+j\)で表すことができるので、
\begin{align*} \log_{2}\left(2^{k}+j+1\right)-1 & \geq\left\lfloor \log_{2}\left(2^{k}+j\right)\right\rfloor \\ & =k\cmt{\because j\in\left\{ 0,1,\cdots,2^{k}-1\right\} } \end{align*} となり、左辺は、
\begin{align*} \log_{2}\left(2^{k}+j+1\right)-1 & =\begin{cases} \log_{2}\left(2^{k}+2^{k}-1+1\right)-1 & j=2^{k}-1\\ \log_{2}\left(2^{k}+j+1\right)-1 & j\in\left\{ 0,1,2,\cdots,2^{k}-2\right\} \end{cases}\\ & \begin{cases} =\log_{2}\left(2\cdot2^{k}\right)-1 & j=2^{k}-1\\ \leq\log_{2}\left(2^{k}+2^{k}-2+1\right)-1 & j\in\left\{ 0,1,2,\cdots,2^{k}-2\right\} \end{cases}\\ & =\begin{cases} \log_{2}2^{k+1}-1 & j=2^{k}-1\\ \log_{2}\left(2\cdot2^{k}-1\right)-1 & j\in\left\{ 0,1,2,\cdots,2^{k}-2\right\} \end{cases}\\ & =\begin{cases} k & j=2^{k}-1\\ \log_{2}\left(2^{k+1}-1\right)-1 & j\in\left\{ 0,1,2,\cdots,2^{k}-2\right\} \end{cases}\\ & \begin{cases} =k & j=2^{k}-1\\ <k & j\in\left\{ 0,1,2,\cdots,2^{k}-2\right\} \end{cases} \end{align*} となる。
これより、
\begin{align*} k & \leq\log_{2}\left(2^{k}+j+1\right)-1\\ & \begin{cases} =k & j=2^{k}-1\\ <k & j\in\left\{ 0,1,2,\cdots,2^{k}-2\right\} \end{cases} \end{align*} となり成り立つのは\(j=2^{k}-1\)のときのみとなる。
従って、\(n=201+m=201+2^{k}+2^{k}-1=200+2^{k+1}\)のときのみ成り立つ。
これより、\(k\in\mathbb{N}_{0}\)として、\(n=200+2^{k+1}\)のとき可決され、それ以外では否決の可能性がある。
また、\(n=201\)のときも可決する。
従って、\(201\leq n\)では、\(n=200+2^{m},m\in\mathbb{N}_{0}\)のとき可決され、それ以外では否決の可能性がある。

補足

これを一般化する。
海賊を\(n\)人、コインを\(m\)枚とする。
\(1\leq n\leq2m+1\)のとき
\(n\)が奇数のとき、配分は、
\[ \left(\frac{2m-n+1}{2},\left(0,1\right)*\frac{n-1}{2}\right) \] となる。
投票結果は賛成\(\frac{n+1}{2}\)、反対\(\frac{n-1}{2}\)となり、全て可決される。
\(n\)が偶数のとき、配分は、
\[ \left(\frac{2m-n+2}{2},\left(0,1\right)*\frac{n-2}{2},0\right) \] となる。
投票結果は賛成\(\frac{n}{2}\)、反対\(\frac{n}{2}\)となり、全て可決される。
\(2m+1\leq n\)のとき
配分は
\[ \left(0,\left(\times\right)*\left(n-2m-1-2^{\left\lfloor \log_{2}\left(n-2m-1\right)\right\rfloor }\right),\left(0\right)*\left(2^{\left\lfloor \log_{2}\left(n-2m-1\right)\right\rfloor }-1\right),?,\left(?,0\right)*m\right) \] となる。
ここで\(?\)記号は今あるコイン\(m\)枚を\(?\)の中から\(m\)人を選んで\(m\)枚を配るということである。
\(\times\)記号は否決をされると次回以降に親分になり否決される可能性がある子分を表し、渡すコインは0枚でいい。
賛成は親分と\(\times\)と\(?\)の中から\(m\)人、反対は\(?\)でコインが0枚の1人、浮動票は配分が0となる子分となる。
これより、投票結果は、賛成\(n-2^{\left\lfloor \log_{2}\left(n-2m-1\right)\right\rfloor }-m\)、反対1、浮動票\(2^{\left\lfloor \log_{2}\left(n-2m-1\right)\right\rfloor }+m-1\)となる。
可決されるか否決されるかは、\(n=2m+2^{k},k\in\mathbb{N}_{0}\)のとき可決され、それ以外では否決の可能性がある。

ページ情報
タイトル
海賊の山分け
URL
https://www.nomuramath.com/f8ykmjso/
SNSボタン