FAQ
RSS
このクイズのヒント
-
ヒント知らないよ
このクイズの参加者（5人）
算数・数学クイズ
算数・数学クイズ
計算
確率
知識クイズ
広告
広告
広告
クイズ大陸関連書籍
|
|
ツイート
|
 プリズン・ブレイク
難易度：★★★★★
 ゲーデル
2010/03/05 14:57
難問です
 。質問事項があれば、どんどんコメントで質問してください  。囁きは、時間がたつごとに（正解に近くなければ）公開していきます  。============================================================================= あなたは IQ180 の天才脱獄者である。色々事情があって、脱獄をしている最中である。 今まで数々のセキュリティーを破り、外部脱出まであと一歩のところまで来た。 しかし、あなたは最後の難所で、立ち往生していた。以下に、現在の状況を示す。 ＜概略図＞------------------------------------------------------------------- ドアA ドアB ドアC ドアD 現在地 --||-- 検査室S --||-- 検査室T --||-- 検査室U --||-- 外部 || はドアである。条件を満たす時のみ開き、一度出ると、自動的に閉まる。通常は閉まっている。 ＜基本情報＞----------------------------------------------------------------- 1. 20人の刑務官が、本来はそれぞれ自分のセキュリティーカード（SC と略）を一枚ずつ 所持していて、SC の表側には固有のカードID (SCID と略)が書いてある。 2. 検査室S と検査室T の2区画に、誰もいなくて、SC も 1 枚もなく、更にドアC が 閉まっている時のみ、ドアA が開く。 3. ドアA が閉まった後、検査室S で、人数チェックとSC の枚数チェックが行われる。 丁度、 1 名と SC 1 枚の時のみ、ドアB が開く。 4. ドアB が閉まった後、検査室T で、刑務官に固有なID (KID と略)と、対応するSC が 一致するかの検査がある。検査方法は、検査端末にKID を入力後、SC を通すだけである。 4-1. KID とSC の対応が一致すると、端末の表示、及び状態がクリアされ、ドアC が開く。 4-2. KID とSC の対応が一致しない時、入力したKID に対応するSC のSCID を "SCID"として、「"SCID"のカードを通して下さい」というエラーメッセージが 端末に表示され、ドアCが開いていればドアCが閉じる。 4-3. 連続で 10 回エラーをだすと、各区画が閉鎖され、警報が鳴る。 4-4. 検査室Tでは、制限時間があり、あまり長い時間をかけていることはできない。 もちろん、10回検査端末を通すくらいの時間的余裕は十分にある。 5. ドアC が閉まった後、検査室U でSC の枚数チェックが行われ、20 枚あればドアD が開く。 6. 検査室T には、様々なセンサーが設置されていて、入室前と退室後で少しでも 差異があると、直ぐに警報が鳴るため、いかなる情報も残すことが出来ない。 7. 各区画の防音/防電波等は完璧で、区画が異なれば、いかなる情報交換もできない。 ＜現状説明＞----------------------------------------------------------------- 8. 上で説明した、基本情報をあなたは知っている。 9. 自分も含め丁度 20 名の脱獄者が「現在地」にいて、あなたはそのリーダーである。 10. 現在、検査室S、検査室T、検査室U の 3 区画には、誰もいない。 11. 刑務官の持っていたSC を20 枚全部手に入れている。 12. KID を 20 個全て知っている。 13. KID と SC の対応が全く分からない。 14. 脱出に使えそうな所持品は、SCだけである。 ----------------------------------------------------------------------------------- さて問題です。 現在地から外部に脱出するための作戦を立ててください。 仲間の脱獄者は、皆頭が良く慎重なのですが 、その反面として、中途半端な説明では納得してくれません  。（つまり、不十分な説明では「惜しい」の評価になります）脱出確率が高い作戦ほど高評価になります。 ====：追記：================================================================= ＊追加条件14.4-4.を加筆しました。(4-4. は 3/8 追記) ヒントを時間が経つごとに、いくつか出そうと思います。(多分5つくらい) １．正攻法で行きます。つまり、現在地で作戦を考え、一人ひとり検査室Ｕに向かって、 検査室Uで20人全員集まり、外部脱出するわけです。(3/6追記) ヒントらしいヒントではありませんが・・・ ２．作戦によって、確率を上げる問題だとお考えください。 全くの無策で行くと、(1/2)^20≒1/1000000で、現実的ではありません。 最初の一人が検査室U にたどり着くのは1/2 ですので、これより大きな確率も望めません。(3/7追記) ヒントにならないヒント第二弾です  次からは、ヒントらしいヒントになりますが、その分、ゆっくり出します  難問ですので、正解発表はまだまだ先の話になります。じっくりお考えください。 ３．次のような作戦はどうでしょうか? 20 個の KID を K1,...,K20とします。 20 名の人は、１枚ずつSCを持って、一人ずつ検査室U に向かいます。 奇数番目の人は、K1,K2,...,K10を調べることにします。 偶数番目の人は、K11,K12,...,K20を調べることにします。 この作戦で成功する確率は、(1/2)^20よりも結構大きくなります。 もちろん、正解はこの作戦よりも優秀な作戦です。 実は、この問題文は、故意的に問題の本質が見えにくくなるよう作っています。 より単純な確率の問題に置き換え、更に適当な緩和条件の問題にすることで、 問題の本質が見えてくるようになるかもしれません。(3/9追記) 正解者が出たので、とりあえず記念ヒント公開です。 今参加している人にはあまり役立たない情報ですが ４．長らく放置しておいて、すみませんでした 。ヒント４公開です！次のような問題を考えてみてください。 1から20まで表に書かれたカードが、ランダムに一列に並んでいて裏返されている。 そこに、20人の人が一列に並んでいて、前からn番目の人が、nと書かれたカードを 当てるゲームをする。もちろん、前の人のゲームの様子はみることが出来ない。 全員が当たれば、賞金がもらえるものとする。 一人につき、10回までカードをめくることが出来る。 めくったカードは、次の人の番になる前に、そのまま裏返しにされる。 ただし、【カードの順番を入れ替ることは可能だとする。】（緩和条件） 20人は、どのような作戦をとればよいだろうか？ 緩和条件がなければ、本質的にこの問題と同じになります。 これが解ければ（ちなみに1/2の作戦です）、正解まであと一歩となります。(8/24追記) ５．最終ヒントです 作戦と考え方ははヒント４．が大ヒントになっていますので、最後は確率計算の仕方についてのヒントにします。 成功する場合を考えるのではなく、失敗する場合はどんな場合なのかを考えると、 簡単に計算できるようになります。(8/27追記) ＊と思ったけど、閲覧してる人すらいないみたいなので、近々公開します。 まだ考えてる途中だから待った！っていう人は、コメントしてください。 １週間は伸ばします。(2010/8/29追記) ★公開しました。
|
回答募集は終了しました。
ゲーデル
できます
。更に言えば、成功した後でKIDだけ入力することも可能ですが、入室前（KIDは入力されていない）と退室後(KID入力済み） で差異がおこると不味い（基本情報6.）ので、結局、検査室U に行かなければ ならないことを考えると、あまり意味がないかもしれません  。基本情報4-1をもう少しだけ明確にしておきますね 追記： 少し勘違いしてたかも 基本的に、検査室Tでは、「KID入力→SC通す」を繰り返すことになります。 
質問です。
ドアCが開いたあと、検査室Uに移動したときに、ドアCは開いたままなのでしょうか？ ドアCを検査室U側から閉める方法がないと、基本情報5の前提を満たせないと思うのですが？
ゲーデル
基本的にドアは一度出るとすぐ閉まるものとお考えください
自動ドアみたいな横スライドドアで、検査室U 側からも 閉めることは可能だと考えてもＯＫです 。すぐ閉まる旨を書き加えますね
ゲーデル
全てのドアは最初閉じているとお考えください
つけたしておきますね。（というか、初めは書いていたんですが、 「自動的に閉まる」と書きなおした時に消しちゃったんです ）
要は１人目が
例えば９回エラーを出したあと １０回目でＳＣ検査をパスしたとして 彼は自分が使ったSC以外の ９枚分のSCIDとKIDの対応がわかっている その情報を現在地にいる１９人に 伝えられればいいわけですね 例えば全員が時計を持っていれば 検査室Uに入るタイミングで 情報の伝達は可能です 例 １人目の所持SCを０ 残りのSCを１～１９ KIDを ABCDE FGHIJ KLMNO PQRST 分秒 0000 1-A 2-B 3-C 4-D 5-E ・・・・・・・・ 0010 1-B 2-A 3-C 4-D 5-E ・・・・・・・・ 0020 1-C 2-B 3-A 4-D 5-E ・・・・・・・・ ・ ・ ・ ・ 5950 １-K 2-F 3-B 4-N ・・・・・・・ こんな感じ 彼が検査室Uに入ると同時に ドアAが開くので 現在地にいる仲間に 組み合わせ情報を伝えられます
それならば
ゲーデル
ナイス解答です！
 予想外の解答で正直驚きました。  しかし、次のような問題があります。 ① 皆、脱獄者ですので、皆が時計を持っていたとは考え難く、 持っていなかった場合は、タイミングを計るのが困難です。 （長めの時間単位でタイミングをとれば、何とかなるかもしれませんが、 その分脱出するまでに長い時間がかかるので、 それは受け入れられないかもしれません。） ② ドアCが閉まるタイミングと、それから検査室センサーでチェックが 行われ、ドアAが開くようになるタイミングは多少ズレルはずです。 そのズレル時間が正確にわからない以上、下手すると 「必ず失敗する作戦」になってしまうので、仲間を説得するのは難しいです。 ＊今後、時計等の小物は誰も持っていなかったと仮定してください。 また、ドアCが閉じて、ドアAが開くまでのタイミングは、何分なのか 何秒なのかも不明なので、時間同期は出来ないものとしてお考えください。 と思っていたのですが、具体的な確率が明示されていないのと、 （「●●」の確率以上にはなる。といったものでＯＫです。） 具体的にどう取り決めるのかの説明が、1～9回目に成功した場合に ついて不十分ですので、仲間はやはり納得してくれないです。 できるだけ公平な評価を期すために、「惜しい」扱いにしますね。 追記： 問題文の所に、現状14.として付け加えておきます。 追記２： 基本情報として、4-4. も付け加えておきます。 検査端末にKID を入力するとき
KIDを打ち込んで最後に ｛ｅｎｔｅｒ｝で決定するとして ｛ｅｎｔｅｒ｝で決定する前に 打ち込まれたKIDは検査端末に 表示されるのですか？ また｛ｅｎｔｅｒ｝を押す前に ｛クリア｝キーなどで 打ち込んだKIDの訂正はできるのか？ 以上の2点がOKなら 開いたドアBを通って 検査室Uに行く前に 検査端末の入力表示を使って 次の人に情報を伝えられるし 次の人は正解がわかった状態で さらに後の人のための調査ができます
では質問です
ゲーデル
まず、最初の２つの質問ですが、
・KID を入力する際、打ち込んだ文字列は表示されると考えて OK です。 ・KID を入力する際、Clearキー等で訂正することも可能と考えて OK です。 しかし、 ＞開いたドアBを通って 検査室Uに行く前に ＞検査端末の入力表示を使って ＞次の人に情報を伝えられるし ＞次の人は正解がわかった状態で ＞さらに後の人のための調査ができます （↑単なる書き間違いだと思いますが、検査室T と検査室U の間のドアはドアC です。) これは、>>1 のコメントにあるように、無理です  。検査室T に入室前：検査端末はクリア状態 検査室T を退室後：検査端末にKIDを入力済み で、検査室Tにある検査端末の状態が異なるので、 基本情報6. により、警報が鳴り響きます。 文字列が表示されていたら当然鳴りますし、たとえ、文字列が表示されていなくても、 端末の状態が異なれば（一番最初のクリア状態になければ）警報が鳴ります 。
>入室前と退室後で少しでも差異があると
これををどこまで厳密に解釈するかですね 1人の人間が短時間でもそこにいれば 室温だって上昇しているでしょう 酸素量二酸化炭素量だって変化してます 検査端末に入力すれば 入力キーに指紋がつきます それらは警告を鳴らす差異にはならない そうですよね？ あれ？そうすると指紋で文字記号を残すことは可能？
ゲーデル
架空の話ですので、
一応、常識的な範囲でお考えください 想定しているのは、ある小さな許容値があって、 それを超えれば警報が鳴るシステムです。 ・温度や湿度等も、許容値を超えれば当然警報が鳴ります。 これらは、退室後に、少しだけ時間を置いて計測することになります。 ・酸素・二酸化炭素等は変わりますが、退室後に、換気がなされるので 意味がないものとお考えください。 ・室内の質量が許容値を超えれば警報が鳴ります。 ・指紋や少しの汗などは、少しであれば、当然許容値の範囲内です。 ・自動認識カメラが色々設置されているので、目に見える範囲で 画像認識的に誤差が許容値を超えれば警報が鳴ります。 ・検査装置の状態がクリア状態かどうかは、検査装置がわかっていますので、 当然変化すれば警報が鳴るわけです。 【許容値がどれくらいかわからない以上、仲間を説得するのは困難です。】 許容値は相当小さいことは、わかっているので、危険すぎるのです。  ただ、情報を残すことが出来る、と仮定して考えを推し進めるのは、 この問題を解くにあたって、無駄にはならないかもしれません。 ただし、基本情報6．によって、実際は、情報を残すことはできません。
どんな部屋にも空気中のホコリが漂い
あらゆる物にホコリは積もります 「ホコリ１つ１つの微妙な位置」は 警報センサーの探知項目外であるはずだ これは十分確信できる推測といえます なぜなら ホコリの微妙な位置までが差異と検出されるということは そもそも人間には差異を残さずに その部屋を絶対に出られない事になってしまうからです そこで検査端末の表示窓上のホコリの位置で 情報を残します ノートPCの液晶画面ってホコりがすごく目立ちますね あれの応用です 道具が使えないなら自分のまつげを2本抜いて それをピンセット代わりに使います 表示窓の上にはじめからある １つ１つのホコリの位置をほんの少し 微妙に微妙にズラしてズラしていくんです ただそれだけでもルールを知ってる人間が見れば 「ホコリが３つ連続してつながった後にわずかなスペース そして２個重なったペアか なるほどなるほど」 こんな感じで暗号として成立します 後に来る者のために情報が残せるならば 最初の1人が１０連続でエラーしない限り 残りの１９人は１００％脱出できます 最初の1人が4回目でKIDが一致しても 彼はすぐに検査室Uにはいかない もう１０連続エラーの危険性はないので すべてのKIDを入力し その結果の情報を残せばいい 成功確率は５０％
指紋でも
小指の先の先のその一部のそのわずか一片の指紋 を規則的に残すことで 情報伝達には十分です 指紋でなくても こんな方法はどうかな？
ゲーデル
まず、前半部分とコメント部分ですが、
埃の位置が何かの拍子に（例えば換気された後で） ずれたらどうするんでしょうか？ 少しでもずれたすると、確率０％になってしまいます。  次の人が入ってきて差異を判断できるのであれば、 カメラによって差異が判断できるものとお考えください。 指紋も、同様です。 次の人が、目に見えて判断できる範囲であれば、 カメラによって差異が認められるわけで、 基本情報6.により、警報が鳴り響きます。 第一、【仲間たちはそれでは納得いかない】ので、協力してくれません  。いつまでたっても評価は「惜しい」止まりになります。 ルールはルールですので、「情報を残さず」確率を上げる作戦を考えてください。 追記： 基本条件4-4. を追加しました。 制限時間は8分くらい（この数字が重要ではありません）とお考えください。
>ずれたらどうするんでしょうか？
簡単です 同じ暗号を２列または３列つくればいい 時間制限も関係ないですね KIDを左右１０づつのグループに分けておき 次にくる人間が持つＳＣのＫＩＤが判明すれば 表示窓の右か左に小指の先の指紋を１つつけておく たったこれだけでも 次の人間の１０連続エラーの危険は回避されます 同じ検査室同じ検査端末を使う以上 警報装置の目を盗んで 情報を残す手段は「絶対に」あります 問題で示された状況では そんな「警報装置の目を盗む手段」を考えることこそ 最も有効であり最も成功率の高い作戦だと思われます それを許さないというのであれば 検査室Ｔと検査端末は使い捨てにすべきでしょう 検査室Ｔは縦に１００個重なっていて 退出者がでるたびに その部屋は廃棄され 新しい部屋が上から降りてくるとか
ゲーデル
基本情報6．の条件は、問題の前提になっていますので、
【絶対に】お守りください。 守らなくてもいいのであれば、 「検査室Uにいる人が、ドアCをノックして情報を伝えればよい。」 （基本条件7.に反しますが、隣の部屋のドアの振動を防げるはずがない） 等といった、色々な屁理屈が通用してきます。 もし永久駆動さんの解答で正解、または別解にしてしまうと、 基本情報6．にある、【いかなる情報も残すことが出来ない】を信じて 考えている他の人が、絶対に納得するはずありません。 どうしても厳密な状況で考えたい、というお考えであれば、 次のように考えてください。 ドアA、検査室S、ドアB、検査室T、ドアC はそれぞれ20個あって、 ドアA 20個と現在地、ドアC 20個と検査室U がつながっているものとする。 ドアB 20個は、ドアAが20個全部閉じ、更に検査室Sのそれぞれに一人と SC１枚ずつが入室した状態でないと開かない。 また、ドアCは、全員が正解しないと開かない。 あとは今とほとんど一緒の条件でお考えください。 ＊ちなみに、この↑の設定は、私がはじめに考えていたものです。 ただし、説明がくどくなるので止めにしました。 今の問題でも結構くどくなっていますが・・・ 20人を適当に10人づつ2つのグループ(グループA,グループB)に分け、20個のKIDを適当10個づつ2つのグループ(KIDリストA,KIDリストB)にわけ、グループAはKIDリストA,グループBはKIDリストBを試行する。
確率は1/C(20,10)=1/184756なので、依然として現実的ではないが、1/2^20よりは高い。
システムの裏を突いて情報伝達する問題ではなくて、事前の作戦によって確率を上げる問題だったのですね。
とりあえず依然として絶望的な確率ですが、確率を上げる方法を考えてみました。 
ゲーデル
＞システムの裏を突いて情報伝達する問題ではなくて、
＞事前の作戦によって確率を上げる問題だったのですね。 そういうことです 問題の骨組み自体はかなり前から出来ていたのですが、色々思うところがあって、このようなややこしそうな問題にしてしまいました。 徹底的に厳密に問題を設計するか、簡明でわかりやすいものにするか、 どちらかにすべきだったかもと、今更ながらちょっぴり反省中です  まぁ中途半端が私らしさといえばそうですけど というわけで（ぇ、とりあえず不正解ですので 後で公開します。 絶望的な確率から、「まぁこれなら仕方ないかぁ」と思える確率に 頑張ってジャンプするのがこの問題の醍醐味です。 20枚のセキュリティカードに1から20の番号を適当につける。
20個のKIDをK1，・・・，K20とする。 n番目に部屋を出て行く人は、n番のセキュリティーカードを持っていく。 1回目はKnを入力してチェックする。 一致していたら終わり。 一致しなければ、エラーメッセージに表示されたSCIDをmとして、Kmを入力してチェック。 これを一致するまで繰り返す。 SCIDとKIDの組み合わせの数は20次の対称群S20の位数に等しい。 S20に属する任意の置換σは互いに素な巡回置換の積に分解できる。 2回目で一致する場合、その２つは互換であり、長さ2の巡回置換。 k回目で一致する場合、それらは長さkの巡回置換。 よって、σが恒等置換、または長さ10以下の巡回置換の積に分解できれば、上記の手順でうまくいく。 これはσの位数が10以下ということと同値。 位数が10以下のS20の元の個数をS20の元の個数で割れば確率が求まる。 S20の元の個数は20!だが、位数10以下の元の個数は・・・
きっとこういう作戦だろうと思います。
具体的な確率を力技で計算する方法は分かりますが、ちょっとやる気にならないですねえ～  まずまずの確率になるとは思うのですが。 簡単に計算する方法があるのでしょうか。 時間がとれたら専門書でも見て勉強してみます。
ゲーデル
一人目の正解者が出そうな感じです
確率計算さえできれば正解です。 ある程度正確な見積もりであれば、「○○」の確率以上にはなる、でＯＫです。 やっぱり、仲間を説得するために、正確ではなくても、 具体的な数字は出して下さい。
1.SCIDとKIDをそれぞれ適当に並べて、対応表を作成する。
2.全員が同じ対応表とカード1枚を持って検査室Tに向かう。 3.各自、自分の持っているカードのSCIDに対応するKIDを対応表から検索して検査端末に入力する。一致した場合は検査室Uへ。 4.外れた場合、検査端末に表示されたSCIDに対応するKIDを対応表から検索して検査端末に入力する。一致した場合は検査室Uへ。 5.上記4.を繰り返す。
こんな手順でやれば、かなり確率を上げられそうです。
なんとなくですが、>>9のような絶望的な確率ではなくて、それなりに成功するかもと思えるような値になるように思います。 具体的な確率値が必要ということなので、別途じっくり考えて見ます。
ゲーデル
そういうことです
あとは確率計算ですね
ゲーデル
惜しいです
ほとんど正解に近いのですが、下から（空行も含め）7,8行目の状況が何を意味するのかを考え直してください。 計算式は、少し変形していけばもっと単純にできることに気づくと思います
KIDをＡＢ１０づつのグループに分けておき
１人目 Ａを試す ２人目 Ｂを試す ３人目 Ａを試す ４人目 Ｂを試す ・ ・ ・ これでわずかだが 成功確率はあがるかな でもあまり変わらないような
＞差異があると直ぐに警報が鳴るためいかなる情報も残すことが出来ない。
という文を 「ため」より前を条件と考え 「直ぐに警報が鳴らないような差異なら情報が残せる」 と私は解釈したんですが 純粋に作戦の問題でしたか
ゲーデル
＞純粋に作戦の問題でしたか
そうなんです 。確かに基本情報6.、基本情報7. は色々言われるかも・・・とか思いながら問題は作りました。 で、囁きの作戦は、確かに無策よりは確率は上がるのですが、やはり まだ絶望的な確率で、不正解となります。
n=20、kを11以上20以下の整数とする。
20次の対称群S20の元σを無作為に選んだとき、その位数がkである確率を考える。 kは11以上なので、σを互いに素な巡回置換の積で表すと、長さkの巡回置換を一つだけ含み、 長さがkを超えるものは含まない。 よってσはk個の項目の巡回置換とそれ以外のn-k個の項目の置換の積として表せる。 逆に、このような積で表せる元の位数がkであることは明らか。 n個の項目からk個を選び出す組み合わせの数は、n!/k!(n-k)! k個の項目の巡回置換の種類は、(k-1)!個 (n-k)個の置換の種類は、(n-k)!個 これらの積が位数がkの元の総数であり、n!/k!(n-k)!×(k-1)!×(n-k)!=n!/k よって、σが位数kである確率は、n!/k÷n!=1/k 従って、σの位数が10以下である確率は、 1-1/11-1/12-1/13-1/14-1/15-1/16-1/17-1/18-1/19-1/20 これが成功する確率を表す式です。 具体的な値は０．３３１２２・・・ であり、１０回に３回は成功しますね。 これなら試してみる価値はあるでしょう。
ちょっと考え方を変えてみたらなんとか計算できる式になりましたので、
具体的な値を計算してみました。 確率の問題では答えは既約分数にするべきだと思いますが、 それは面倒なのでやめておきます。 面白い問題でした ところで、このシステムだと外部から中に入ることができないと思います。 ある意味完璧なセキュリティですが。 
ゲーデル
おめでとうございます！
完璧です。 ＞このシステムだと外部から中に入ることができないと思います。 実は最初の方で考えていたのは、脱出劇ではなく、ルパン大作戦 だったんです。 今の問題の「外部」に当たる所に機密情報があり、更にそこで、一方通行の状態を 逆向きに変更できるようなシステムを考えていました。 ただ、そうすると、不必要な部分の説明のために約1.5倍近くなるので中止に... というわけで、刑務官達の緊急外部脱出のための場所を利用した脱出劇 という想定の問題になってます
ゲーデル
いえ、たぬきおやぢさんは、99.99%正解にたどり着いてるんです。
実際に、○○の場合の状況を具体的に作ってみて、 作戦を実行してみてください。何が起こるかすぐ分かるはずです。
ゲーデル
そういうことです
No.12を少し訂正すれば、正解となります
ということで、
(1-Σ[K=11,20](COMBIN(20,K)*FACT(K-1)*FACT(20-K)/FACT(20)) より答えは。0.331228597 一流打者の打率くらいですか。これなら説得できそうですね。
やっと到達。かな？
ゲーデル
おめでとうございます
正解です。
（準備）
SCを適当に①から⑳と番号をつける。 KIDも適当に番号をつけて、No.1～No.20とする。 これを各人しっかりと覚えておく。 ただし、これらは勝手に番号をつけただけなので、ほとんどが正しく対応していない。 （実践） 検査室Tではまず、各人が持っているSCと同じNoを割り振ったKIDを入力する。 一致しなければ、そのときに端末に表示されるSCIDの番号を見て、それに対応するNoのKIDを入力して、再度挑戦する。 これを最大10回、ドアが開くまで繰り返す。 （具体的には…） 例えば④のSCを持っているなら、No.4のKIDを入力してカードリーダーに通す。 これでドアロックが解除されればOK。 解除されない場合は、例えば「⑧のSCIDのカードを通してください」と表示されるので、次はNo.8のKIDを入力して④のSCをカードリーダーに通す。 これを各人ドアが開くまで繰り返す。
考え方があっているのか分からない状況での計算はめんどくさそうなので、
まず作戦を囁きます
ゲーデル
そんな感じです
確率計算頑張ってください
閲覧してる人すらいないみたいなので、近々(今月中に)解答を公開します。
「まだ考えてる途中だから待った！」とか「今から考え始めたから待った！」 っていう人は、コメントしてください。 最低１週間は伸ばします。
【解答】
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 が示されることを正解の基準にしました。 ）★何か質問があればお気軽にどうぞ★ ＝＝：追記：＝＝＝＝＝＝＝＝＝＝ なんか私一人の解答じゃわかりにくいかも、という事で、 正解者（手順、確率計算、別々）の囁きも公開しておきました。 （公開なんてするな！ボケっ！ って人は、他の問題でもいいから、囁きでコッソリ知らせてください。コッソリ非公開に戻します。 ） |
問題へジャンプ