アパマンショップ浜松東店

こんにちは、東店、近藤です。
５人の海賊の問題の解答はこうです！



答え：{98,0,1,0,1}

考え方としては
以下のように、海賊の人数n を順々に増やして考える。
最上位から順に、親分、2位、3位、4位、、と呼ぶ。
上位の人から順に取り分を記述することにする。

一人の場合
{100}

ふたりの場合
親分（＝分配する超本人）さえ賛成すればよい
{100,0}

３人の場合
親分は少なくともあと一人に賛成してもらう必要がある
- 2位は二人の時を考えて『親分さえ死ねば自分に100枚の金貨が手に入る』ことを知っているので、
親分が100枚自分に分配しない限り、確実に反対する。
- 一方、3位はやはり二人の時を考えて『親分が死ねば、確実に自分は分け前なし』だということを知っているので、
１枚でも金貨がもらえればその案に賛成する。
よって貪欲な親分は必要最小限の１枚の金貨を3位に渡す。
{99,0,1}

この考えを繰り返すと答えは見えてきます。皆さんは正解にたどり着けたでしょうか？