【解答】
20 個の KID を K1,...,K20 、また、20 個の SCID を S1,..,S20 とする。
作戦は次の通りである。
20 名にそれぞれ 1 枚ずつ SC を渡し、K1〜K20 とS1〜S20 を全て覚えてもらうか、
覚えきれなければ、何らかの方法でメモしてもらう。
そして、1名ずつ現在地から検査室U に向かう。
検査室T で、n (n = 1,...,20) 番目の人は、次のようにする。
まず、自分と同じ番号(n)の Kn を入力し、SC を通す。
ドアC が開かなければ、エラーメッセージの Sm と
同じ番号(m) の Km を入力し、SC を通す。
ドアC が開くまで、これを繰り返す。
ドアC が開いたら、痕跡を残さないようにして、速やかに検査室U に移動し、
20人全員が検査室U にたどり着いたら、全員で外部脱出する。
この作戦で、成功確率は、0.331 (約1/3) になる。
以下その理由を示す。
(K1,...,K20) に対応する SC の SCID を (Sσ(1),...,Sσ(20)) とした時、
(1,...,20) 上の置換 σ=(σ(1),...,σ(20)) を考えることが出来る。
エラーメッセージによって、ある n についてσ(n) が判明するので、これを利用する。
一旦 10 回の回数制限を忘れると、
ある n に対して、高々 σ を 20 回やれば、必ず n に戻ってくる。
さて、M(n) (≦20) 回 n にσ を適用すれば、n に戻ってきたとする。
ループ中に出てきた全ての数字を同じグループとすると、
1〜20 をいくつかにグループ分けすることが出来る。同じグループに属する場合、
丁度 M(n) 回 σ を適用すれば、元に戻ることになる。
全てのグループが M(n)≦10 を満たしている場合、本作戦は成功し、
逆に、M(n)≧11 のグループが存在する場合、本作戦は失敗する。
置換の総数 20! の中で M(n)≧11 のループが存在する場合を数え上げてみる。
σ が決まれば、 M(n) が 11 以上のループは高々 1 つしか存在ない。
また、長さ k のループの個数は、(20! / (20 - k)! ) / k で、
残りの 20-k 個の順列は (20-k)! 通りあるので、
失敗するのは、
Σk=11..20( 20! / ( (20-k)! k) (20-k) ! ) = 20!
Σk=11..20 1/k 通り。
よって、成功確率は、 1 -
Σk=11..20 1/k ≒ 0.331
-----------------------------------------------------------------------------
1/3 というと、低いように見えますが、一人目が検査室U にたどり着ける確率が 1/2
である事を考えれば、20 人でそれだけあれば、そう悪くない確率です
。
一般に、2n 人の人がいてn回まで検査できるものとすると、外部に行ける確率は
1 -
Σk=n+1..2n(1/k) となり、
n→∞ とすれば 1 - ln 2 ≒ 0.306853 となります。
問題文の主人公は、ln 2 ≒ 0.693 を暗記していたらしく
、
1 -
Σk=11..20(1/k) ＞ 1 - ∫
12(1/x) = 1 - ln 2 ≒ 0.307
として、3 割より大きいことを直ぐに評価し、仲間を説得したみたいです
。
10人で並列計算して甘めの評価(5刻みの計算)をすれば、暗算に近い事も普通に可能で、
p = (1000 -
Σk=11..20 1000/k )/1000
＞ (1000-95-85-80-75-70-65-60-60-55-50)/1000
= ((100-95)+...+(100-50))/1000
= 5 * (1+3+4+5+6+7+8+8+9+10)/1000
= 5 * 61 / 1000 = 0.305
により、3 割よりは大きいことは楽にわかります。
（ということで、p ＞ 0.3 が示されることを正解の基準にしました。
）
★何か質問があればお気軽にどうぞ★
＝＝：追記：＝＝＝＝＝＝＝＝＝＝
なんか私一人の解答じゃわかりにくいかも、という事で、
正解者（手順、確率計算、別々）の囁きも公開しておきました。
（公開なんてするな！ボケっ！(・o・‖)って人は、他の問題でもいいから、
囁きでコッソリ知らせてください。コッソリ非公開に戻します。
）
20 個の KID を K1,...,K20 、また、20 個の SCID を S1,..,S20 とする。
作戦は次の通りである。
20 名にそれぞれ 1 枚ずつ SC を渡し、K1〜K20 とS1〜S20 を全て覚えてもらうか、
覚えきれなければ、何らかの方法でメモしてもらう。
そして、1名ずつ現在地から検査室U に向かう。
検査室T で、n (n = 1,...,20) 番目の人は、次のようにする。
まず、自分と同じ番号(n)の Kn を入力し、SC を通す。
ドアC が開かなければ、エラーメッセージの Sm と
同じ番号(m) の Km を入力し、SC を通す。
ドアC が開くまで、これを繰り返す。
ドアC が開いたら、痕跡を残さないようにして、速やかに検査室U に移動し、
20人全員が検査室U にたどり着いたら、全員で外部脱出する。
この作戦で、成功確率は、0.331 (約1/3) になる。
以下その理由を示す。
(K1,...,K20) に対応する SC の SCID を (Sσ(1),...,Sσ(20)) とした時、
(1,...,20) 上の置換 σ=(σ(1),...,σ(20)) を考えることが出来る。
エラーメッセージによって、ある n についてσ(n) が判明するので、これを利用する。
一旦 10 回の回数制限を忘れると、
ある n に対して、高々 σ を 20 回やれば、必ず n に戻ってくる。
さて、M(n) (≦20) 回 n にσ を適用すれば、n に戻ってきたとする。
ループ中に出てきた全ての数字を同じグループとすると、
1〜20 をいくつかにグループ分けすることが出来る。同じグループに属する場合、
丁度 M(n) 回 σ を適用すれば、元に戻ることになる。
全てのグループが M(n)≦10 を満たしている場合、本作戦は成功し、
逆に、M(n)≧11 のグループが存在する場合、本作戦は失敗する。
置換の総数 20! の中で M(n)≧11 のループが存在する場合を数え上げてみる。
σ が決まれば、 M(n) が 11 以上のループは高々 1 つしか存在ない。
また、長さ k のループの個数は、(20! / (20 - k)! ) / k で、
残りの 20-k 個の順列は (20-k)! 通りあるので、
失敗するのは、
Σk=11..20( 20! / ( (20-k)! k) (20-k) ! ) = 20! Σk=11..20 1/k 通り。
よって、成功確率は、 1 - Σk=11..20 1/k ≒ 0.331
-----------------------------------------------------------------------------
1/3 というと、低いように見えますが、一人目が検査室U にたどり着ける確率が 1/2
である事を考えれば、20 人でそれだけあれば、そう悪くない確率です
一般に、2n 人の人がいてn回まで検査できるものとすると、外部に行ける確率は
1 - Σk=n+1..2n(1/k) となり、
n→∞ とすれば 1 - ln 2 ≒ 0.306853 となります。
問題文の主人公は、ln 2 ≒ 0.693 を暗記していたらしく
1 - Σk=11..20(1/k) ＞ 1 - ∫12(1/x) = 1 - ln 2 ≒ 0.307
として、3 割より大きいことを直ぐに評価し、仲間を説得したみたいです
10人で並列計算して甘めの評価(5刻みの計算)をすれば、暗算に近い事も普通に可能で、
p = (1000 - Σk=11..20 1000/k )/1000
＞ (1000-95-85-80-75-70-65-60-60-55-50)/1000
= ((100-95)+...+(100-50))/1000
= 5 * (1+3+4+5+6+7+8+8+9+10)/1000
= 5 * 61 / 1000 = 0.305
により、3 割よりは大きいことは楽にわかります。
（ということで、p ＞ 0.3 が示されることを正解の基準にしました。
★何か質問があればお気軽にどうぞ★
＝＝：追記：＝＝＝＝＝＝＝＝＝＝
なんか私一人の解答じゃわかりにくいかも、という事で、
正解者（手順、確率計算、別々）の囁きも公開しておきました。
（公開なんてするな！ボケっ！(・o・‖)って人は、他の問題でもいいから、
囁きでコッソリ知らせてください。コッソリ非公開に戻します。