20 Prisoners and 12 Boxes [English Subtitles] 

論理クイズと調べるとよく出てきます

オセロのやつとかね

クラスメイトの名前と出席番号覚えるみたいなもんやろ

作戦会議は自由なんだしいくらでも時間貰えるでしょ

作戦会議に100年使えばよくね?

@@user-bq5dw1cb4i意外と１ヶ月経っても思い出がない人は名前が曖昧なんてざらにあるのに、どうやって作戦会議だけで覚えるのよ エグい犯罪履歴でリンク…させられるか…？

@@user-oi5yg3nk8v www

馬鹿でも60%は引ける(期待

@@spark0122全員で協力してやっと5割なのに、そいつが6割にかけたら全体の成功確率は約3割になるのでは…

普通に考えたら、作戦や名前を覚えられない奴いるよな笑。実際は数字じゃないから、ミスの可能性は当然高くなる

俺の記号はRだから…えーっと…あれ？なんだ？この箱を10回くらい開ければ良いって話だったっけか？ 分かんね。こんな時いつも元カノのユリにやらせてたからなあ。 →全員道連れ

この動画の戦略が最適であることは次のように証明できます。 元のゲームを次のように改変した新しいゲームを考える。 ・各囚人が開けた箱は、ゲーム終了まで開いたままになる。 ・自分の名前が書かれた箱が既に開いている場合、囚人はそれ以上箱を開けずに退出する。 このとき以下の(1)(2)(3)がいえる。 (1) 新しいゲームは元のゲームより簡単になっている。正確に言うと、元のゲームの戦略をそのまま新しいゲームに持ってきて、箱を開ける権利が余ったらランダムに開けることにすれば、成功確率は上昇することはあっても減少することはない。つまり、戦略sの元のゲームでの成功確率をw(s)、新しいゲームでの成功確率をw'(s)とすると、w(s)≦w'(s)。 (2) 動画の戦略はこの簡単化の恩恵を受けない。各囚人が入室した時、自分のサイクルの箱は全部開いているか全部閉じているかのどちらかである(サイクルを中途半端に開いた者がいたらその時点で全員処刑なので)。よって箱を開ける権利が余ることはなく、動画の戦略をDと書くとw(D)=w'(D)。 (3) 新しいゲームには実は戦略性がない。囚人間で伝わらない情報がないので実質一人用ゲームと考えてよく、開けられていない箱を開ける時はどれを選んでも優劣がない。よってどの戦略を取っても成功確率は同じで、w'は定数関数。 (1)(2)(3)から、元のゲームのどんな戦略sについてもw(s)≦w'(s)=w'(D)=w(D)が言えるので、Dは元のゲームの最適戦略(の一つ)。

面白いですが、これは立派な「コミュニケーション」だろうと言わせてください。 （実際には一人あたりの制限時間（5分など）があって、前の人の退出時間にかかわらず常に10分ごとに呼ばれたりすると思います。）

13以上のループ作れば良いだろと思ったが名前と数字の紐付けがわかんねえのか

RU-vidなんて見てないできちんと罪を償ってください

つまんねえ 友達いないんかな

色々草

​@@trnyahb2928 ネタか本気か微妙なラインw

ゲームするか提示されなきゃ死刑執行されるだけでは...？()

Permutation graph ですね。 （Functional graph は各頂点の入次数が 1 とは限りません（同じ名前のカードが複数枚あるかもしれない状況に対応します）。）

まあ数枚確認した時点で法則に気づけるやろから、よほど融通の利かない囚人が紛れ込んでない限り生き残りそう

意図的にサイクル増やせないならずらしても……

えぐすぎ 天才かよ

左から順に名前をつけるんじゃないの？

各々の箱を開ける確率の平均化にこそ、この問題の肝がありそうな気がする。 全員が1～12の箱だけを開いたら100%に死刑になるから、そういった可能性を極力排除するためになるべく別々の箱を開けてもらう。 それで指針として、「初めにあける箱」「次に開ける箱」を定義することで開けられる箱を分散した。 なので「アタリの箱・ハズレの箱」の場合は次に開けるべき箱が分からなくなるので提示された方法は使えなくなる。

そうですね。箱の中身を見ることができない（係員が代わりに確認してYes/Noのみ伝えられる）場合、生存確率は 0.6^20 よりは多少上げられそう（アタリの箱が人によってすべて違うことはわかっている）ですが 0.5 に到達するのは不可能そうです。

@@kaj694 どうやら説明が分かりづらかったようです。要するに私が言いたいのは、中に入っている「人の名前」の有無で動画内で提示された方法が可能になるかが変わるはずだということで、これだとこのコメントに返信してくれた人と内容は被るのですが、いくら箱に番号付けしたとしても箱のサイクルという指針を失うので運否天賦になるはずです。

例えば「1234, password,... みたいなありがちなパスワードに対するハッシュ値はあらかた計算されてる（つまり、容易に割れるため使うべきではない）」っていう現状があるけど、これはこの動画の問題に対応させると「特定の番号を含むループ/チェーンに、ある番号が出現するか否かが事前にバレてる」みたいな状況（想定より有利な戦略が存在してしまう）みたいな感じになるの……か？

箱を13個まで開けられる場合、58.2%になります

@@nibitas 個数ミスか！w

コンピュータで試行しましたか？

@@user-dq3ht9st5h力技の可能性探るの笑う

200万人もどこから連れてきたんだろう

n箱のループができているときに箱の中身を一つずらしてもループであることは変わらないから、n箱でのループの場合の数が円順列で求められるんだと思う。

円順列と、箱でのループの作り方が一対一に対応します。 例えば時計回りに 1 4 5 3 2 という並びと「箱1に名前4、箱4に名前5、箱5に名前3、箱3に名前2、箱2に名前1」という入れ方が対応します。 （なお n=5 はやや大きく、n=3 や 4 の方が分かりやすいと思います。長さを過半数にしたかったのでやむを得ませんでした。 例えば n=3 の場合、円順列は「1 2 3」「1 3 2」の 2 通りで、入れ方は「箱1に名前2、箱2に名前3、箱3に名前1」「箱1に名前3、箱2に名前1、箱3に名前2」の 2 通りです。）

@@evimalab なるほどです！ ある箱からループ順に辿っていったとき、ある箱の次に来るものは何通りあるか？というのを考えると、たしかに(n-1)!になって円順列のパターンと対応できますね。 箱1,2,3…の順で考えると綺麗にいかなかったので、こういうやり方あるんだなと勉強になりました。ありがとうございます！

死んでて草

多分こんな感じ？ その場合、 7個まではこのルールに従って開ける。この時点でまだ無理だったら今選んでるのが13以上のループということは分かる。このまま続けると確定で失敗するからここで、このルールは使えなくなる。 残り選択権は5回で、後の箱は13個、そのうち、最後に引いた名前のやつは取る意味が無いから、 残りの箱は12個ということになる。そのうち、少なくとも5個が正解にたどり着ける。 その中からテキトーに選んで、先程のルールに従って開けていく。 １回目 成功確率は5/12 関係ないループだと分かったら残りの中からテキトーに、… 2回目 成功確率は (無関係ループ1なら)4/11、残り4回 (無関係ループ2なら)3/10、残り3回 (無関係ループ3なら)2/9、残り2回 (無関係ループ4なら)1/8、残り1回 みたいな感じで考えていけばよさそう

俺も「入ってた番号の位置の箱を開ける」という手順の上でループが成り立つ場合を考えると、看守が大きいループを意図的に仕込めば死刑に持ち込めるという点がひっかかったんよね。 で、死刑囚ワイ閃いた。これって特定のループをみんなが同じ順に辿れればOKだから、例えば「入ってた番号の位置の、２つ右隣を開ける」とかでも本質的にはOKで、箱の配置が決まった後でこの手順を相談して決められるなら看守が（未知の手順における）ループを仕込めないってことになるのかな？ とっ散らかってすまん。つまり看守有利な配置パターンが存在するなら（逆説的に）それをハックして勝率上げられるかもと思ったが、そうではなさそうということが言いたかった。

@@waka630 確かにその通り むしろ2個右に限らず、Sを1〜20の自然数の集合としてf:S→Sの全単射として利用することに決めれば、看守はfをピッタリ当てないと行けなくなるのでほぼ不可能

しかし、「『引いた番号の位置の箱を開ける』戦略を想定した看守がループ20を仕込んだ」とわかっていれば対抗して「引いた番号＋１の位置を開ける」なら2倍速でループを進めるから間に合う！？ いやそれだと途中で番号を飛び越しちゃう可能性が50%くらいありそう？　でも12回開けるなら終盤２周目でも拾えるかもだし50%以上の勝率になるか？

@@waka630 というか今更だが看守は名前と番号の紐付けがどうなってるか知らないから、意図的にループ作るのは無理ってのはあるな。w

含まれないはずです。（箱1に名前2、箱2に名前3、…、箱12に名前13、箱13に名前1が入っている場合、名前1～13の人は全員箱1～13をすべて開けます。ほかの入れ方でも1つのサイクルをなす限り同様です。）

​@evimalab ごめんなさい。やっと理解できました。 13個の箱に番号を割り振ることの出来る全ての場合を数えているものと勘違いしていました。 サイクルになっている=どの囚人もサイクルの最後の箱で自分の番号に到達する　というのが良くできているなと改めて思いました。 それが分かったことで4:43のテーブルの数え方と繋がりました。 ありがとうございました。

雑な説明 囚人番号と左端からの順番が一致した状態から位置を移動させることで所長の問題の状況を作ったと考える｡ n番囚人のカードがa1の位置に移動したとしたらそこにあったカードは別のa2に移動していてそのa2にあったカードはa3に…と辿っていくと 同じ位置に二枚のカードが来ることはないのでいつか必ずnの位置に戻って来てサイクルn→a1→a2…→ax→nが成立する そして囚人がやっているのはこのサイクルをaxから逆に辿るのと同じなのでいつかはnのカードにたどり着ける

サイクルというと何か難しくなるように感じます。 最初に自分の番号の箱を開けているため、 自分の番号を引かない限り、引いた番号の箱は開いていない状態であり、次の箱を開けることができる。 これを繰り返していけばいつか自分の番号が入った箱にたどりつきます。

最初に自分の番号の箱を開けてるため、割り当てられるループには必ず自分の名前が含まれます

@@mayo8930言おうと思ってたこと言われた

@@mayo8930 そっか、自分の番号の箱に戻ってくるんだから、ループ上の１つ前の箱には必ず自分の番号が入ってるもんね

20進数で考えて、n箱目でiが出たらI+20^n秒待つほうが効率的ですよ

0:50

勝率が50%を超える戦略が「ある」こと（動画の戦略をとると失敗確率が50%未満になること）を証明しています。（最適かはわかりません。）

@@evimalab失敗確率が50%を超えてなかったんですね、読み違えていました

なんか確実に田中は田中を含むサイクル引けるみたいな雰囲気出てるけど、そんなことなくね？ 他人含むサイクル引く確率の方が圧倒的に高いし、それ考慮したら生存確率かなり下がるくね？

11箱のサイクルなら、11番目に開ける箱に「田中」が入ってるよ。そうじゃないとサイクルにならないので

動画内の説明4:00あたりによれば、 「13箱以上のサイクルがなければ全員生存は正しい」以下ではこれが誤りであることを示す。 ここで、 例えば、箱番号1→2→...→12のサイクルAと箱番号13→14→...→20のサイクルBがあるとする。ここで、番号1の名前「20さん」がいた時、「20さん」は自分の名前を引けない これは13以上のサイクルがないけど死ぬという具体例である。

動画内の説明は 『・13以上のサイクルがない場合、絶対に全員生存 ・13以上のサイクルがない確率は0.5以上 よって、全員生存する確率は0.5以上である。』というものである。 しかし、前述のように第一の仮定が誤っているため、この証明は誤っている ....どう...？

その設定で言うと、12番の箱に「20さん」が"必ず"入ってる いやいや、13～20番の箱に入ってるかもしれないじゃん、◯ぬじゃん、と思うかもしれないけど、それはありえない。1番の箱を開けたなら最終的に1番の箱に戻ってくるルート、つまり12番→1番のルートが存在して、そのためには12番の箱に「20さん」が入っていなければならない よって、動画内の「13箱以上のサイクルがなければ全員生存する」は正しい