難問論理クイズ「幼女と金貨の山分け」

ついに有名問題が登場です。

難問ですが、きわめて鮮烈な論理的解答が存在します。

さあ、論理クイズ界でも評価の高い良問にチャレンジしてみましょう!

問題

5人の幼女(ABCDE)が100枚の金貨を山分けする。

20枚ずつ分割すれば話は早いのだが、他の分け方をすることにした。

1人が案を出し、それを多数決で「採用」か「不採用」かを決め、採用されればその分割案が適用される。

A>B>C>D>Eの順に発言力があるので、この順番で幼女たちは「分割案」を提案していく。

流れとしては以下のようになる。

  1. 幼女Aが分割案を提案する
  2. 幼女全員で多数決を取り賛成が半数以上なら採用
  3. 不採用の場合、幼女Aは追放される

次は、残った4人の中で最も発言力のあるBが分割案を出し、同様のことを分割案が採用されるまで繰り返す。

幼女たちはきわめて論理的である。
幼女たちは誰も追放されたくない。
幼女たちは自身が追放されない限り、なるべく多くの金貨が欲しい。
幼女たちは賛成しても反対しても自身の取り分が変わらない場合、反対する。

このとき幼女Aはどのような戦略を取れば最も多くの金貨をもらえるか。

さあ、解いてみよう!

元となった問題は「海賊と金貨」としてよく知られています。

少し簡単に思えますが、実際に考え始めてみると予想以上に難しいことが分かります。

基本的に、幼女たちはAの提案に反対したいはずです。
1人が追放されればそのぶん自分の分け前が増える可能性が高まるので。

幼女Aは生半可な提案をしてはいけません。

以下では「問題のポイント」「ヒント」「正解」と続きます。

ご自身の力でチャレンジしたい場合は、「問題のポイント」まで読むだけに留めましょう。

問題のポイント

分割のシステム

  1. 幼女Aが分割案を提案する
  2. 幼女全員で多数決を取り賛成が半数以上なら採用
  3. 不採用の場合、幼女Aは追放される

この問題最大のポイントとなるのが、山分け案の分割システム。

たとえば幼女Aが、ABCDEの取り分を(20,20,20,20,20)にする分割案を提案したとします。

これを採用するかどうかを幼女Aを含む全員で多数決を採り、賛成が半数以上ならその分割案が採用されます。

不採用なら幼女Aは追放され、残った幼女BCDEで同じことを繰り返します。

全員で多数決
賛成が半数以上なら採用

という点が特に重要になるので、注意して考えてください。

幼女の優先順位

幼女たちは誰も追放されたくない。
幼女たちは自身が追放されないなら、可能な限り多くの金貨が欲しい。

幼女たちの行動指針は、まず第一に「追放されないこと」。

そして追放されない状況であれば、可能な限り多くの金貨を得ようとします。

この問題で「追放」とは「分割案が賛成半数以上を得られず却下されること」を意味します。

つまり、すべての幼女は––問題文でカギとなる幼女Aももちろん––「この案なら多数決で賛成半数以上を得られる」と確信できる分割案を提案しなければならないのです。

きわめて論理的な幼女

幼女たちはきわめて論理的である。

「幼女の論理クイズ」シリーズにおいて、必ずと言っていいほど述べられるこの一文。

幼女とは「幻ノ女」の略称であり、論理クイズの世界に登場する驚異的な論理・演繹思考を持つ幻想上の存在です。

この問題の幼女たちも、「もしここで賛成票/反対票を入れると何が起こるか」ということをきわめて論理的に先々まで読んで行動します。

ヒント

第1のヒント

いきなり問題文の状況を考えようとしても、うまくいかない

第2のヒント

幼女が2人の場合を考えてみよう

第3のヒント

「0枚」と「0枚じゃない」は大違い

最後のヒント

1枚も金貨をもらえない幼女がいる

 

 

 

 

正解


幼女ABCDEの取り分を、Aから順に
(98,0,1,0,1)
とした時、幼女Aは賛成多数で金貨98枚を入手できる。

解説

幼女Aは、「多数決で過半数を取れる分割案」を出さねばならない。

この前提からすると、幼女Aが入手できる98枚という金貨はあまりにも多すぎます。

なぜ、この分割案が賛成多数を得るのでしょう?

幼女が2人の場合

幼女ABCが追放されて、DEしか残っていない場合を考えてみましょう。

この時、幼女Dは(100,0)という提案をすることで確実に金貨100枚を入手できます。

(100,0)という分割案では、Eは1枚も金貨をもらえません。
当然Eは反対します。

しかし、ルールでは
「全員で多数決を取り賛成が半数以上なら採用
とあります。

賛成:反対=1:1なので、賛成が半数以上により分割案は採用されます。

このことから、もし幼女がDEの2人になってしまった場合、幼女Eは金貨を1枚も得られないということが分かります。

幼女が3人の場合

幼女ABが追放されて、CDEしか残っていない場合を考えてみましょう。

この時、幼女Cは(99,0,1)という分割案を提案するのが最適戦略です。

幼女Dは、幼女Cさえ追放すれば金貨100枚を得られるので「自分に金貨100枚を与える分割案」以外はすべて反対します。

幼女Eは、Cを追放してしまうと自分に金貨は1枚も入りません。
それゆえ幼女Eは、幼女Cがたとえ1枚でも自分に金貨を分けてくれたら賛成するのが最適戦略なのです。

幼女が4人の場合

幼女Aが追放されて、BCDEしか残っていない場合を考えてみましょう。

この時、幼女Bは(99,0,1,0)という分割案を提案するのが最適戦略です。

幼女Dは、Bを追放してしまうと自分に金貨は1枚も入りません。(幼女Cが99,0,1という分割案を出すことが読めているため)
それゆえ幼女Dは、幼女Bがたとえ1枚でも自分に金貨を分けてくれたら賛成するのが最適戦略なのです。

幼女が5人の場合

ようやく問題文の状況にたどり着きました。

以上の展開から考えると、幼女Aは「自分が追放されたら1枚も金貨を手に入れられない幼女」に最低枚数1枚を与えて票を獲得すればいいわけです。

幼女Aが追放され、BCDEの4人になった時に1枚も金貨を得られないCとEに1枚ずつ……。

(98,0,1,0,1)という分割案を提出することで、幼女A,C,Eの賛成票は全体の半数以上を占め、この案は無条件で受け入れられるのです。

まとめ

こういうね!

「一見どう考えていいのか分からないけど単純なモデルから考えていくと論理的に答えが出る問題」

ってすごく楽しいですよね!!

数学どころか算数の知識もいらないってのがまた素晴らしい!!!

あーーーーー生きててよかったーーーーーーー。

参考

幼女問題まとめ – Gist

さまざまな論理パズルをまとめていらっしゃるcatupperという方のGist(ソースコード共有サービス)。
本論理クイズは、こちらの4番目のテキストファイル「04.幼女の山分け」から問題文の要旨を引用いたしました。

Puzzle 20 | (5 Pirates and 100 Gold Coins)

Wikipedia:Pirate game

解答の参考に活用させていただきました。

140字以内の問題文

幼女ABCDEが100枚の金貨を山分けする
ABCDEの順に分割案を出す
多数決で賛成が半数以上なら採用されるが不採用なら提案した幼女は追放される
幼女は自分に利益が生じる時に賛成する
幼女は追放されたくないが、自分が追放されない場合に限り最大限の金貨が欲しい
幼女Aはどうする?