からみあう幼女3人の思惑。
単純そうに見えるこのゲームの戦略を、そこから生じる複雑な結果を、あなたは見抜けるでしょうか。
問題
1000枚のクッキーがある。
幼女A,B,Cの3人は、Aから順に好きなだけクッキーを取っていく。
これをクッキーがなくなるまで繰り返す。
1回に取るクッキーは、必ず1枚以上。
幼女たちには以下の本能がある。
#1. 幼女はできるだけ多くのクッキーを取りたい。
ただし、波風を立てるのはイヤなので「最も多くクッキーを取った人」にはなりたくない。
また、「クッキーが最も少ない人」にもなりたくない。
#2. 自分が#1を満たせないと確信したら、なりふり構わずできるだけ多くクッキーを取ろうとする。
#1は、#2よりも優先される本能である。
#1を満たした幼女は「勝者」と言っていい。
幼女たちは全員きわめて合理的である。
互いにコミュニケーションは取れないが、誰がいくつ取ったかは分かる。
さて、幼女Aが勝つにはいくつクッキーを取ればいい?
また、その場合の幼女B,Cのクッキーの取り分はどうなる?
さあ、解いてみよう!
3人が順番にクッキーを取っていく。
この単純なルールに基づいて行われる行動は、そのかなりの範囲を制限されています。
少し考えてみると予想以上に厄介なことに気づくでしょう。
では、問題のポイントを振り返ります。
問題のポイント
2位じゃないとダメなんです
#1. 幼女はできるだけ多くのクッキーを取りたい。
ただし、波風を立てるのはイヤなので「最も多くクッキーを取った人」にはなりたくない。
また、「クッキーが最も少ない人」にもなりたくない。
幼女たちの目的は、「自分より多くクッキーを取った人がいる」「自分より少なくクッキーを取った人がいる」状況で、「自分はなるべく多くのクッキーを取る」というもの。
#1と題されたこの本能は、他の何よりも優先されます。
彼女たちにとっては、2位になる(その上で可能な限り多くのクッキーを取る)ことが最重要の使命なのです。
そのため、
幼女A:2枚(2位)
幼女B:1枚(3位)
幼女C:997枚(1位)
という状況がありえるとするなら、幼女Aだけが目的を達成したことになります。
幼女たちが2位を目指すのは最優先事項。
「なるべく多くクッキーを取った2位」を全員が目指しています。
2位になれない時は
#2. 自分が#1を満たせないと確信したら、なりふり構わずできるだけ多くクッキーを取ろうとする。
「どうやっても自らが2位になれない」と理解した時、幼女たちはその時点で確保できるクッキーを全て取ります。
勝ち目がないなら一矢報いる。
素晴らしい闘争本能です。
ヒント
第1のヒント
幼女Aが取るクッキーの枚数が「1」「333」「1000」の場合から考えると効率がいい
こういった問題において、効果的なのが「極端な数字」や「境界線となる数字」を当てはめて考えてみること。
そこで出た結論は、ある一定の範囲の数字にも応用できるはずです。
第2のヒント
幼女たちはきわめて論理的である
登場する幼女たちは、とても論理的です。
ある状況下で何手も先を読み、「自分に#1は満たせない」と確信した時点で#2の本能を実行します。
幼女Aが何枚クッキーを取るかで、幼女BCがどんな最適戦略を取るかは変化してきます。
幼女たちの思考を先読みして考えてください。
第3のヒント
割と重要なのが「幼女たちは必ず1枚以上のクッキーを取る」という点
幼女Cがクッキーを取ってもまだクッキーが残っていた場合、幼女Aからまた順にクッキーを取っていきます。
この時、幼女たちは必ず1枚以上のクッキーを取らねばならないというルールが見た目以上に大切な役割を果たします。
当然のように見えるこの一文は、ある状況下においては特定の人物のマイナスに働いたりします。
第4のヒント
1巡目で勝負がつく
2巡目は訪れません
最後のヒント
ひとつもクッキーを取れない幼女がいる
正解
幼女A:334
幼女B:666
幼女C:0
解説
方針を立てよう
一見して知識問題ではないと分かります。
純粋に、論理的思考を積み重ねていくしかなさそうです。
とはいえ1000枚のクッキーの分割パターンを逐一調べていくわけにはいきません。
時間がかかりすぎるので。
こういう時は「極大の数字」「極小の数字」「境界線付近の数字」から考えていくと効果的です。
幼女Aが1000枚のクッキーを取った場合
この場合の内訳は
幼女A:1000
幼女B:0
幼女C:0
「自分よりクッキーの数が多い人」がいないので、幼女Aは勝者になれません。
2位になることが何よりも優先されるので、幼女Aにとってこの選択肢はありえません。
幼女Aが1枚のクッキー(幼女に取れるクッキーの最小数)を取った場合
この場合の内訳は
幼女A:1
幼女B:
幼女C:
残り:999
この時、幼女Bは2枚以上のクッキーを取るわけにはいきません。
1位になってしまうからです。
幼女Bは1枚だけクッキーを取ります。
幼女A:1
幼女B:1
幼女C:
残り:998
この時、幼女Cも2枚以上のクッキーを取るわけにはいきません。
1位になってしまうからです。
幼女Cは1枚だけクッキーを取ります。
幼女A:1
幼女B:1
幼女C:1
残り:997
ここから幼女Aにターンが戻りますが、全員1枚しか取れない(2枚以上取ったら1位になってしまう)ため、最終局面では以下のような内訳になります。
幼女A:333
幼女B:333
幼女C:333
残り:1
次はAのターンですが、合計クッキー数が1位になってしまいます。
つまり「2位になれなかった」ため敗北です。
2位になることが何よりも優先されるので、幼女Aにとってこの選択肢はありえません。
幼女Aが333枚のクッキーを取った場合
1000を3で割ると333.333…
おそらく多くの方が「このあたりに問題のポイントがある」と見抜いて、333付近の数字を調べることからスタートしたと思います。
本記事でも、本格的な解説の出発点を「333」としましょう。
まず幼女Aが333枚のクッキーを取った場合から考えていきます。
幼女A:333
幼女B:
幼女C:
残り:667
ここで幼女Bの状況を考えてみましょう。
幼女Bが2位になるためには
「334以上のクッキーで2位」
「333のクッキーで2位」
「332以下のクッキーで2位」
のいずれかの状況が必要です。
幼女Bが334枚以上のクッキーを取ると、幼女Cはそれより1枚少ないクッキーを取り幼女Cが2位(勝者)になってしまいます。
幼女Bが333枚のクッキーを取ると、幼女Cは332枚のクッキー(幼女Aより1枚少ない)を取り、残りは2枚の状態でAに順番が回りその時点で#1を満たせないからAは#2を実行し幼女Bが2位(勝者)になることが確定するためそれをあらかじめ見抜いた幼女Cは#1を満たせないため#2を実行するので勝者なし。
幼女Bが332枚以下のクッキーを取ると幼女Cは332枚のクッキー(幼女Aより1枚少ない)を取り幼女Cが2位(勝者)あるいは勝者なしになってしまいます。
つまり、幼女Aが最初に333枚しかクッキーを取らなかった場合、少なくとも幼女Aに勝ち目はありません。
そしてこれは、幼女Aの取るクッキーが333枚以下(>=2)(※1枚の場合は記述済)の場合でも同じことが言えます。
この状況では、
「幼女Aのクッキーの枚数 – 1」
のクッキーを取ることが幼女Bの最適戦略となり、その時も同じ展開をたどり幼女Aの勝ち目はなくなります。
ようやくひとつの結論にたどりつきました。
幼女Aは333枚以下のクッキーを取ると敗北する。
幼女Aが335枚のクッキーを取った場合
幼女Aが335枚のクッキーを取ると何が起こるでしょう?
幼女Bは334枚のクッキーを取ります。
そうすると幼女Cには331枚しか残りません。
幼女Cは#1を満たせないので、#2に従って残りの331枚を全て取ります。
ここで3人のクッキーの内訳を見ると
幼女A:335
幼女B:334
幼女C:331
となり、幼女Bが2位になり勝者となります。
つまり、幼女Aが335枚のクッキーを取ると幼女Aは敗北するわけです。
さらに重要なことに、幼女Aが335枚以上のクッキーを取っても上記の流れをたどって幼女Aは敗北します。
幼女Bは、常に幼女Aより1枚少ないクッキーを取ればいいわけですから。
※幼女Aが501枚以上取った場合、幼女Bは残りのすべてのクッキーを取ればいい
幼女Aは335枚以上のクッキーを取ると敗北する
幼女Aが334枚のクッキーを取った場合
※ここから話が複雑になります
333枚以下でも、335枚以上でもダメ。
では、幼女Aが334枚のクッキーを取った場合を考えていきましょう。
幼女Bが333枚のクッキーを取ったと考える
幼女Bが、「幼女Aを1位にして自分は2位になるべく」333枚のクッキーを取ったとしましょう。
幼女A:334
幼女B:333
幼女C:?
残り :333
この時点で幼女Cは#1を満たせなくなります。
幼女Cが2位になるためには、幼女B(最下位)の333枚を超える334枚が必要です。
しかし幼女Cに残されたクッキーは333枚のみ。
ここから、#1を満たせない幼女Cは#2に従って残りの333枚を全て取ります。
最終的な内訳は以下の通り。
幼女A:334
幼女B:333
幼女C:333
この結果は、幼女Bにとって致命的損失です。
幼女Bが333枚を取っても幼女Bは#1を満たせないことが分かっているからです。
自分が確実に#1を満たせない状況である時、幼女は#2を実行します。
すなわちこの条件下では自分のターンが来た時点で幼女は#2を実行し、666枚のクッキーを取ります。
ここで、幼女Bの取るクッキーが「334枚」「335枚以上」の場合も見てみましょう。
幼女A:334
幼女B:334
幼女C:332
幼女A:334
幼女B:335
幼女C:331
前者でも幼女Bは2位になれず、後者に至っては幼女Aが2位になる手伝いをしてしまうことになります。
「333枚」でも「334枚」でも「335枚以上」でも……
すなわち、幼女Aが334枚を取った時、幼女Bは333枚以上取ると#1を満たせなくなります。
幼女Bが332枚のクッキーを取ったと考える
では、幼女Bが332枚のクッキーを取ったとしましょう
幼女A:334
幼女B:332
幼女C:?
残り :336
この時、幼女Cは333枚のクッキーを取ることで2位になります。
幼女A:334(1位)
幼女B:332(3位)
幼女C:333(2位)
残り :3
そしてまたAから順番にクッキーを取っていくわけですが、幼女たちは必ず1枚以上のクッキーを取らねばならないという制約があるため、現時点で最多数のクッキーを持つ幼女Aはどうしても1位になってしまい、#1を満たせず#2を実行します。
幼女A:334+3(1位)
幼女B:332(3位)
幼女C:333(2位)
つまり、幼女Bが332枚のクッキーを取ると幼女Cが2位(勝者)になってしまうため、幼女Bは#1を満たせないことが確定的になります。
すなわち、幼女Aが334枚を取った時、幼女Bは332枚取ると
#1を満たせなくなります。
そしてこれは、幼女Bの取る枚数が332枚以下でも同じことが言えます。
幼女Bが332枚以下のクッキーを取る時、幼女Cは必ず333枚のクッキーを取ります。
幼女A:334(1位)
幼女B:x(≦332)(3位)
幼女C:333(2位)
残り:333-x
幼女Cは、「幼女Aより1枚少なく」「幼女Bより何枚か多い」クッキーを確保することになり、必然的に幼女Cが2位(勝者)となります。
結論として、幼女Aが334枚を取った時、幼女Bは332枚以下のクッキー取ると#1を満たせなくなります。
「幼女Aが334枚のクッキーを取った場合」の幼女Bの状況まとめ
以上をまとめると、幼女Bは
- クッキーを333枚以上取ると#1を満たせなくなる
- クッキーを332枚以下取ると#1を満たせなくなる
となり、どうしても#1(2位になること)を満たせなくなります。
ここで幼女Bは#2の本能を実行し、残るすべてのクッキー(666枚)を取ります。
正解まとめ
幼女Aは334枚を取る。
幼女Bは2位になれないことが確定するので残り全てのクッキー(666枚)を取る。
幼女Cはひとつもクッキーを取れない。
幼女A:334
幼女B:666
幼女C:0
まとめ
なんか割と複雑でした。
参考サイト
140字以内の問題文
クッキーが1000枚ある
幼女ABCの3人はAから順に好きなだけクッキーを取る(1枚以上)
1.幼女は多くのクッキーが欲しいがクッキー獲得数で2位になりたい
2.自分が1.を満たせないとわかったら最大数のクッキーを取る
幼女Aが勝つには?
その場合のBCの取り分は?