呪いのかばんパズル

alice in the git stash @koteitan

Q. 1,000,000個のカバンの中に１つだけ呪いが入っています。あなたができるのは昼間にそれを好きなように２つに分けて、家来のいる部屋といない部屋に入れることです。家来のいる部屋に呪いのカバンが入ると家来は夜の間にダメージを受け、あなたは翌朝それが分かります。(続く)

alice in the git stash @koteitan

家来が６回ダメージを受けるとそのゲームはあなたの負けです。呪いのカバンを一意に特定できるとそのゲームはあなたの勝ちです。他人に先に見つけられると負けです。同着１位は勝ちです。勝率の一番大きな戦略は何でしょうか？(他人の行動は見れないものとします)

alice in the git stash @koteitan

ちなみに自分以外のプレイヤーは１人だとします。

alice in the git stash @koteitan

俺も正解知りません

Tamejirou @Tamejirou

100万個のカバンを1日でどうにか動かせるほどの労力があるなら他にもっとやることあるだろ 100万枚のコイン、ならまだ分からんでもない

ミトコ🫥みや @SuTsmw

@koteitan その他人は、自分と同じくこの問題で与えられた条件の行動しか出来ないんですか？

alice in the git stash @koteitan

常に１つだけ家来の部屋に入れる戦略だと、呪いのカバンが見つかったときには即決できるけど平均50万回くらい試行しないといけないので、常に２つ家来の部屋に入れる戦略に負ける

Kanrokoti @Kanrokoti

これ勝ち戦略あるの？取り敢えず単純に二分探索でやっても31250個のカバン余して負け。 twitter.com/koteitan/statu…

alice in the git stash @koteitan

@skytouhou111 はい。決めた行動を繰り返します。ただ、異なるゲームの経過によって自分の行動を変えるのはOKです

Tamejirou @Tamejirou

とりあえず6回、二分していけば15625個には絞り込めるのか。この時点で家来のダメージ値は0−6の間で期待値は3。

alice in the git stash @koteitan

@kanrokoti 「いつもひとつだけ家来の部屋に入れる」だと、一応家来が１ダメージ受けた直後に呪いのカバンが判明するので勝てます。

ミトコ🫥みや @SuTsmw

@koteitan なるほど... あともう一つ、その他人は論理的に最も正しい行動をしますか？

Kanrokoti @Kanrokoti

@koteitan でも勝率低いですよね

alice in the git stash @koteitan

@kanrokoti はい。低そうですね。

Tamejirou @Tamejirou

かと言って単純に二分していくのでは、期待値的に12回も試行する頃には家来は死んでしまうし、その時点で244個程度にしか絞り込めない

alice in the git stash @koteitan

@skytouhou111 はい。要は考えうる中で一番勝率が高い戦略を取ります。

alice in the git stash @koteitan

@kanrokoti まじですか。これさっき私が作ったパズルで誰も答えは知りませんので言ってもらってOKです

超法のシャングリラさん @ShangriLa_P

@koteitan 6回ダメージを受けるとだめ。最初の検知で1回まで食らえるとして、残り4回。だから、2の4乗が32なので32個入れるのが必勝しながら最善になります。これで4回とも外れても勝ちます。あとは、どれだけリスクとるかですね。

Tamejirou @Tamejirou

仮に平方根である1000個ずつ入れていく方法ではどうか。一旦見つかれば次は32個、その次は5−6個程度に絞り込める。仮にライバルが居なければ何日(何年)かかっても良いのだから、4回以内の試行でたどり着ける。しかし時間がかかりすぎるな。

Kanrokoti @Kanrokoti

@koteitan 問題をチューリングマシンで置き換えて神託機械取っつけて…ってのは冗談ですが、ランダムにカバンを一つ選択し、それを家来の部屋に入れる、というのが理論上最強ではないでしょうか(ボゴソート的な意味で)実際の勝率というか、実用性は皆無でしょうけど

Tamejirou @Tamejirou

逆から考える。2個、4個、、と増やして行けば2^5は32個、2^6は64個。一度に64個ずつ取って行けば、家来は死ぬことがない……のか？

Tamejirou @Tamejirou

呪いを12回も検出することはルール上不可能だったわ

alice in the git stash @koteitan

@ShangriLa_P 2^4=16なので16ずつが本意ですか？

超法のシャングリラさん @ShangriLa_P

@koteitan そうですね。小学生レベルの算数ができてなくて申し訳ないです。