やぎさん郵便

質問

昔から分からない問題があります。
　牢獄の別々の部屋に幽閉された金庫破りの２人AとB。ドアをこじ開けるのは簡単です。もし両方が同時にドアをこじ開ければ、多分両方とも脱出できる。でも一方だけがこじ開けたら確実に射殺されてしまう。この２人、廊下を毎日掃除する雑役囚を買収して手紙で通信している。でも雑役囚が必ず手紙を届けるとは限らない。届くなら出した翌日の朝に届きます。さて、
A「Ｂさんへ。いよいよこじ開けようと思う。でもこの手紙が着いていないと困るので、返事を下さい。返事を受け取った日の正午のサイレンを合図に実行します。」
B「了解。でもこの手紙が着いていないと困るので、返事を下さい。返事を受け取った日の正午のサイレンを合図に実行します。」
A「了解。でも....」
これじゃダメですね。この二人、どういう手紙を書けば確実に同時にドアをこじ開けることができるか？（手紙は届かないかもしれないんですよ。）

回答No.14

nanashisan · ベストアンサー

なかなかわがままな質問者ですね。
ARCさんの回答でだいたい分かりそうなものですが…。
＞決行直前に窓から何か物を投げることにしておき、相手が投げたものが自分の窓から確認できれば、作戦決行する。
これは確かにわからんですが。

では、
手紙のやりとりがあり、ｎ通目の手紙で決行日が決まったとします。
ｎ通目の送信者は返事を待たずして決行日が確定するわけですから、
ｎ通目の手紙が届いたかどうか分からなくても、
すなわちｎ通目の手紙が届かなくても決行できるわけです。
これはｎ－１通目以前に決行日が決まっていたことになり仮定と矛盾します。
故に、決行日が決まるｎは存在しない。

お礼

わーnanashisan様に怒られちゃった。

> 決行日が決まるｎは存在しない
という証明。なるほど納得しちゃいますが、でもAstroiaさんの方式を実行してみたとして、手許に
「何度でも言うが決行はX月XX日正午。もう10通同じ手紙を受け取った。たまには別の話も書け」
なんて手紙がわさわさと溜まっている、という状況になっても、やっぱり決行日が決まっていないのかなあ？
　Astroiaさん方式において「全然意志疎通が出来ていない。失敗。」という事態を確実に識別する方法（Nakaさんが試みたような）がない（？）ということが本質的なのかなあ？つまりAstroiaさん方式を開始すること自体が博打？これとnanashisanさんの証明とが繋がってるような気がします。
どうも、わがままでごめんなさい。

回答No.18

noname#254

えと…「ギモンの（１）」について。
> Ｂからの返事がＡのもとに届いて以降は、むしろ雑役囚が手紙を届けられる
>確率は低いほうが有利
　ここ、「単に手紙を出さない」だけです。Ｂからの返事を受け取った日から、Ａは手紙を送るのをやめる。その「沈黙」自体が「受け取ったよん」という合図。で、その沈黙がシュレちゃんのサボリのせいか、それともＡが手紙を書いていないせいかの判断が、「確率が低い方が」判断しやすい（日を追うにつれて、しやすくなる）、ということです。
「ギモンの（２）」について。
>この文学的確率方式は、AとBの立場が対称ではない。AはBの返事を貰った
>時点で通信が往復したことを100%確信できるが、Bはそうじゃない。
　Ｂは100％の確信には至りません。が、Ａの沈黙の日数が重なるにつれて、「おれの返事がＡに届いている」可能性が100％に漸近していく、とは言えると思います。
　で、「ギモンの（３）」。
>もし200１年大晦に至ってもAがついにBから返事を貰えなかったら、翌日Aと
>Bは何をする？
　はい。ozapan試案はここで自爆します。そのような事態になったら、脱出計画はabortするしかありまへん。またやりなおし…。で、わてもやりなおしでんがな…。

補足

> 脱出計画はabortするしかありまへん。またやりなおし…。

abortしてやりなおすのは一向に構いません。むしろ、確実に双方がabortと判断できるかどうか、そのためにはどういう取り決めを提案すべきか、が問題じゃないのかなあ...

回答No.17

nanashisan

stomachmanさんともあろうお方が何をおっしゃいます。
確率がすごく高いことと100%を混同しているだけでは？

補足

> 確率がすごく高いことと100%を混同しているだけ
そおかなあ。いやホントに分かんなくなってまして。

Bの受け取った手紙１「Bへ。俺はX月X日に決行する。１月１日」
Aの受け取った手紙１「Aへ。わかった。俺もX月X日に決行する。１月７日」
Bの受け取った手紙２「Bへ。了解。X月X日だ。１月９日」
Aの受け取った手紙2「Aへ。X月X日に会おう。１月１２日」
ここまで来ちゃえば実行可能では？
最初の手紙は、返事が届かなければ多分「嘘」になるだろう。でも１往復半行き来したところで、双方が通信の往復を確認できる。２往復で双方が「双方が通信の往復を確認したこと」が確認でき、１通目と２通目の意味は確定する（んじゃなかろうかしらもしかして）。んで、ここまで至らない内に期日が来てしまう可能性、ここんところが博打であり、ところが博打を回避しようと凝った文面にすると決行日が保留されたままになってしまう、という構造なのかなあ？

回答No.16

conrad

読み間違えていたら見逃して下さい。
>「質問のような間抜けな通信を既に１００回繰り返し、その間手紙が届かなかったことは１度もなかった、という実績がある。」
１００回に一度は届けられると読みました。
ＡがＢに初日から２０１日目を決行日と通知すれば良いような…

補足

>１００回に一度は届けられると読みました。
微妙に違います。１００回中１００回届いた実績がある。でも、必ずいつも届くという保証はない。
言い換えれば「返事が来ないという場合、こちらからの手紙を相手が受け取ったのか、受け取らなかったのか、両方の可能性がある。」

回答No.15

noname#254

試案です。結局、「確率勝負」の域を出ていません。だから自信はありません。

　作戦開始日時を2001年一月一日とし、脱出決行日時を2002年一月一日とします。
　で、Ａ（アラン）からＢ（ビル）への手紙。
「我が友、ビルへ。
　私はこれから毎日、以下の同じ文面の手紙を君に送りつづける。君から返事がくるまでだ。そして君から返事が来たら、その日から私はこの手紙を送るのをやめる。私からの返事がなかったなら、そのこと自体、私が君からの返事を受け取ったことを示すメッセージだと考えてくれ。逆に言えば、もし私からの返事が届いたら、それはまだ君からの返事を受け取っていないということだ。「了解した」…その一言でいい。毎日返事を書き続けてくれ。
　…そう、もちろん、君が懸念するように、雑役囚のシュレジンガーは手紙を届ける時もあれば届けない時もある（彼もリスクを負っているからね、悪いことは言えない）。だから私からの返事が届かなかったからと言って、それが確実に「私が了解した」ことを意味するわけではない。だが、考えてみてくれ。
　仮にシュレジンガーが手紙を届けない確率を二分の一としよう。私が返事を送っているにも関わらず、君のところに届かない確率は、初日では二分の一、次の日には四分の一…ｎ日後には１/２のｎ乗になっている。10日後なら1024分の１だ。…どうかね？　ここまでくれば、私が君に「返事を書いていない」ことはかなり確実と考えていいのではないかね？　つまり君は、私の「沈黙」が続けば続くぶんだけ、外の広い空の下で思いっきりうまい空気を吸う期待をふくらませていいわけだ。
　では決行の日時を伝える。ちょうど一年後の2002年一月一日。この日だ。…お雑煮…昆布巻き…お煮しめ…伊達巻…数の子…ああ、考えるだけで生唾がわいてくる…。
　では、君からの返事を待っている。
　ああ、それから、手紙の末尾に添える日付にはくれぐれも注意してくれ。日付をチェックすれば、私の返事が君のもとに届いたのが単なる行き違いなのか、それとも本当に君の返事が届いていないのかはわかるはずだ。シュレジンガーは、届けるとすれば、必ず翌日の朝に届けてくれるからね。
　無事に出られたら、一緒にエレーンの店に飲みに行こう。…彼女のこと、まだ勝負はついていないからな。

　　　　　　　　　　　　　　　　　　　　君の誠実なる友、アランより。
　　2001年一月一日
」

　…という感じです。
　お分かりと思いますが、この場合、Ｂからの返事がＡのもとに届いて以降は、むしろ雑役囚が手紙を届けられる確率は低いほうが有利になります。ですから、例えばワイロの額を減らしてシュレジンガーさんにへそを曲げてもらうとか、あるいはまったく届けるのをストップしてもらうことが可能ならば、確実になってきます。…でも、これはルール違反でしょうね。

　Stomachman師匠。けっこー必死こいて考えましたが、ご批判を仰ぎます。

補足

ozapanさん！いらっしゃいませ。
　さすが名文だなあ。格調高いなあ。AlanとBillでしたか。（赤井と馬場かと思ってました。）Alanは日本食好みなんですねえ。その上、雑役囚が生きてるんだか死んでるんだかわからないブキミな奴だとは思いもよりませんでした。エレーンの介護をどっちがやるか、早く決めないとエレーンが寿命で召されてしまいますね。

　さて、これは確率の問題として捉えた場合の一つの案。Astroiaさんの方式の変奏曲ですが....
ギモンの（１）
> Ｂからの返事がＡのもとに届いて以降は、むしろ雑役囚が手紙を届けられる確率は低いほうが有利
ここのとこ、ちょっと変だな。手紙が届く確率を０にするには単に手紙を出さなければ良い。
ギモンの（２）
この文学的確率方式は、AとBの立場が対称ではない。AはBの返事を貰った時点で通信が往復したことを100%確信できるが、Bはそうじゃない。
ギモンの（３）
もし200１年大晦に至ってもAがついにBから返事を貰えなかったら、翌日AとBは何をする？

　nanashisanさんへのお礼に書いたように、ひとたび、通信が少なくとも１往復行き来し（成功し）たことを双方が確認できたら、実行可能になるようにも思われます。
　従って問題は、将来通信が成功するかどうか分からない状況でどういうプロトコルで試行を始めるか。通信が失敗したことをどうやって認識し、その場合にどう行動するのか、そのプロトコルを作れるかという点にあるように思われます。逆に失敗の可能性をプログラムに入れると、通信の成功が確信できているのに決行日に相手が決行すると確信できない、という状況が必然的に生まれるんだろうか。（nanashisanさんの恐怖の証明のように。）
　stomachmanとしてはこの問題のジレンマの根元、エッセンスを見つけたいんです。
とまれ、ハードボイルド小説の一コマのような素敵な手紙。有り難うございます。

回答No.13

ARC

>はて、これを許したら旨く行くんでしょうか？よく分からないです。

まず、何回か手紙をやり取りしてX日の正午に決行する。ただし、以下のような取り決めを行っときます。

1:昼のサイレンがなったらまず、牢獄の窓から何か物を投げる。

2:相手の部屋の窓から物が投げられるのを見れば、もう数個窓から物を投げる。

で、決行の当日に相手の部屋の窓を観察し、投げられたものが０または1個なら実行は中止、2個以上なら決行すればいいと思います。

回答No.12

motsuan

基本的に確率的にしか決められないのではないでしょうか？

Ｎ回連続して手紙を渡したとき雑役囚が
少なくとも１回は手紙を渡す確率が１となる回数をＮとします。

このとき、Ａはまず
「Ｂが指定する日にちに決行しよう」
という文面を最悪Ｎ回送り続けます。
Ｂは初めて受け取った日からＮ日後に
決行することに決めて、
その日付を書いた手紙をＡにＮ日間送り続けます
（Ｂが親切であれば
　手紙を書いた日付も付けておくでしょう）。
あとは信頼関係の問題だと思います。

こうして最短でＮ＋１日、
最長で２Ｎ日で確率１で脱出が可能となります。

でも問題にしたいのはこんな場合ではなくて
Ｎが無限大の場合なのでしょう。
この場合、相手に自分の出した手紙が渡っていることを
確認する方法を見つければよいという問題に帰着すると思うのですが
確率的にしか相手に手紙が渡らないのであれば、
確率的にしかそれを知る方法がないと思うのですが．．．
雑役囚に手紙を出すとか．．．

補足

有り難うございます。
うーむむ。
Nakaさんの方式のように「通信が失敗と分かれば、延期してやり直す」のはアリなんです。この点を無視すればまさに仰る通りのように思われますが...

回答No.11

ARC

(#4の補足)
>AもBもそう簡単に不可能と諦める積もりはなさそうです。なんとか助けてやってくださいな。

この問題に関しては、先に書いたように、雑役夫を使う(遅延の生じる通信手段を使う)限り、理論的に解決不能なんです。

他の方が書いておられるような、成功率を高める為の工夫はいろいろと出来るでしょうが、どのような手段を用いようとも最終的に決行直前にお互いに通信できないことには、「確実な」脱獄は不可能です。

#4でも書いたように、キーとなるのはこの部分なんです。
事前にどれだけ打ち合わせを重ねようと、どれだけ周到に通信の確実性を追及しようと、最終的に決行直前に知りたいのは、その瞬間の相手のやる気でしょう。
通信手段の遅延によって生じた、1日前の相手のやる気が参考にならないというのであれば、通信手段を変更する以外に道はありません。

AとBに残された道は、
1:相手に対する信頼と、リスクに対する覚悟を身に付ける
2:代わりとなる通信手段を見つける
のいずれかでしょう。

例えば、決行直前に窓から何か物を投げることにしておき、相手が投げたものが自分の窓から確認できれば、作戦決行する。とか。

お礼

度々のご回答、本当に有り難うございます。

確かに、エンターテインメントではなく数学カテゴリーにポストしている以上、
> 解決不能
が証明できれば、それで立派な解であると思います。

> 決行直前に窓から何か物を投げることにしておき、相手が投げたものが自分の窓から確認できれば、作戦決行する。
はて、これを許したら旨く行くんでしょうか？よく分からないです。

回答No.10

taka41

さっきのすんません。B側からはわかんないですよね。。。
あさぢえこいちゃいました。

回答No.9

taka41

こういうのはどうでしょう？
まず、AがBに「次は手紙を2通送ります。
次に受け取った手紙のうち、1通をその場で私に送り返して下さい。」
という手紙を1通送ります。
次に、AはBに2通手紙を送ります。その2通の手紙には対になるIDと
「あすの消灯時刻に脱獄する」と書いておきます。
雑役囚がBからの手紙を返して来た時に手紙のID番号から、
その対になる手紙が前日にBに出したものであるかどうかが解ります。
っていうのでどうでしょう？
stomchmanさんに回答するのはひじょーに気が引けるんですが。。。

回答No.8

Naka

◆Naka◆
すみません、変数「ｚ」が抜けていました。
先の回答をもう一度、引用して付け加えます。

『この下の文はいつも同じ文面で書きます。あなたも同じ文面を書き写して書いてください。今日から１日おきに書きつづけますので。ただし下の「ｘ」の部分は１回ごとに２ずつ確実に引いてください。（初期値は10になっています）また「ｙ、ｚ」の部分には、それぞれ正しい数を記入してください。「ｘが２以下」の状態で「ｙが１以下」または「ｚが０」のときは、さらに10日後に延期します。その場合は、ｘ＝０になった翌日に、ｘ＝10、ｙ＝０、ｚ＝０に戻します。

決行は「ｘ＝10」日後の正午のサイレンとします。
AはBからの手紙を「ｙ＝０」通受け取りました。
BはAからの手紙を「ｚ＝０」通受け取りました。』

と思ったんだけど、あれえ～？？？
やっぱり一筋縄じゃいかないなぁ…

補足

Nakaさんへの補足の場を借りて、ちょっと問題を整理します。

・AとBはある期日までに脱出したい、という訳ではない。とにかく「そのうち」出られれば良い。
・もし「他方が今日の正午に必ずこじ開ける」と確信していたら、自分も必ずこじ開けるものとします。せっかくのチャンスを逃がす気はA,B共ないし、相手がそうであることを双方は確信している。
・一方がこじ開けたのに他方がこじ開けない、という事態は、どんなに小さな確率であろうと絶対に避ける。
・双方が永久にこじ開ける可能性がない、というのではもちろんダメ。
・手紙が届く確率は結構高いが、100%じゃない。

Aが「BがX月XX日の正午に実行するに違いない」と確信でき、しかも
Bが「AがX月XX日の正午に実行するに違いない」と確信できる。
という状況を作ることができれば良い訳です。

たまに届かないことがあるにしても、双方向に通信できているんですよ。これって、実はごく普通の通信となんら変わるところはない。それなのに、なんでこんな簡単(そう)なことが出来ないんだろう？？？？