囚人さんのオンオフ
-
＜ため息さんちでのハンニバル・フォーチュンさん出題パズル＞
｛一部文字レベルで修正｝
２３人の囚人のグループが刑務所の食堂に集められて、次のように言われる。これから全員がそれぞれ独房に入れられたのち、スイッチつきの電球がひとつだけある部屋で一人ずつ取調べを行う。囚人たちはその電球を点灯または消灯することであとから入ってくる囚人とやりとりしてもよい（そして、それだけがやりとりをする唯一の手段でもある）。電球の明かりは部屋の外に漏れない。最初、電球は消えている。取調べは決められた順序で行われるものではなく、取調べの間隔も決まっておらず、どの時点においても、それまでに何度か取調べを受けた囚人がまた取調べを受けるかもしれない。囚人は取調べを受けるとき、電球のスイッチをそのままにしておくか、あるいは点灯・消灯させることができる。
囚人の誰かが取調べを受けるときに、２３人の囚人全員がすでに取調べを受けたと宣言することが目標である。（その宣言は無理に行わなくてもよい）。その宣言が正しければ、囚人は全員釈放されるが、間違っていれば、全員が処刑される。独房にはいる前に食堂に集められた囚人たちは、（この場限りで互いに相談しておくことが許されているが、）自分たちが釈放されるような事前の取り決めを交わしておくことができるだろうか。以上、名著「１００人の囚人と１個の電球」から引用しました。
-
先頭記事が更新されました。
-
@riffraff 自己レス
＜雑談コーナーでの澪標書き込み＞
各人に点滅回数に対応した一意の「ばいなりーこーど」を付与しこれに従って行動。＜尋問時に自分に付与されtコードに遭遇した際に、点滅を逆にし、それ以外のケースはなにもしない。＞上記初等解の図
-
@riffraff 自己レス
これだめです。自爆!(^^)!
-
超お馬鹿な解を発見!(^^)!
しじふの点灯士
❶２3人中１名を点灯士に任命します
点灯士のお仕事：①電灯が消えていれば点灯②点灯回数をカウント・記憶
❷残りの２２人を滅灯人と呼びます
滅灯人の役目：①尋問に出頭時、電灯が消えている事態に最初に遭遇した際にのみ滅灯
❸23回の点灯を行った後、おもむろに”全員漏れなく尋問しましたね”、と答えるあまりにお馬鹿です。(;'∀')
-
惜しい！
実に惜しいです！
①最初、電球は消えているんです。②《滅灯人の役目：①尋問に出頭時、電灯が消えている事態に最初に遭遇した際にのみ滅灯
》いや、滅灯時に滅灯できません。
-
「１００人の囚人と１個の電球」では、バリエーションとして、《取調室の電球のオンオフの状態を、囚人たちは事前の合議の段階では知らない》という問題をも解説しています。
囚人が３人の場合で結構ですので……
-
@Hannibal さん
問題読み違えではありません!(^^)!
点灯士のお仕事：①電灯が消えていれば点灯・・・以下略
しじふの消灯士（謎）にくらべれば半手間増えますので、最短候補ではありませんね(;'∀')
追加問題考えてみます。
これからの続きはこのスレッドにします。雑談コーナーでは先ほどの書き込みを最後とします。
話は変わりますが、Christopher Beckwithと言う中央ユーラシアの言語・歴史学者がいます。博覧強記というかHomo Unibersalisとでも呼ぶべきかたですが、その方の高句麗語に係る著作＜
Koguryo, the Language of Japan's Continental Relatives＞をひょんなことから入手しました。読み始めた所ですが面白い。ベースになる中古中国音の復元が、カールグレン以来の方法とも日本中国学の方法とも異なる、同時代並行言語（チベット語等）をベースにしていいます。（まだ流し読み始めたばかりですので、その妥当性についてはなんともいえませんが刺激的です。）
-
@Hannibalさん
明滅不明問題：
ますます通信工学の問題に見えてきました。
3人のケースを書きますオマジナイ
A ドラマー
B フォロワー１
C フォロワー２
消灯状態0 点灯状態１とします
Aの作業：（0）→１→0→１
Bの作業：＜1→0→１＞を検知して１→0
Aの作業：0→１→0→１→0→１
Cの作業：１→0→１→0→１を検知して１→０
全体としては
（0）→１→0→１→0→１→0→１→0→１→0
又は（0）→１→0→１→0→１→0
又は（0）→１→0→１→0→１→0→１→0クロック制御に信号を織り込む方式を思い出しました
雑談
もう一つ思い出したのは暗号史上の都市伝説
ポーランドの通信士がドイツ第三帝国の公用通信にパルチザン間の情報連絡をハートビートや確認エンヴェロープにまぎれこませた。
-
@riffraff さん
明滅不明問題3人のケースの御回答について書きます。
RE:オマジナイ
A ドラマー
B フォロワー１
C フォロワー２
消灯状態0 点灯状態１とします
Aの作業：（0）→１→0→１
Bの作業：＜1→0→１＞を検知して１→0＝＝
確認したいのですが、思うに、
本解の意図としては、Bの作業よりも先にCの作業が行われないようにしたプロトコルなのですよね？そのことを前提にお尋ねいたします。
取調べが行われる順番はランダムですので、
Aの作業：（0）→１→0→１
の各段階の全てをCのみが知っていて、Bは知らないこともあろうかとは思うのです。
たとえば、Bは、
Aが三回取り調べを受けた局面で、つまり
（0）→１→0→１
において
一回目のスイッチングと二回目のスイッチングが行われたことを知らないでいて、三回目のスイッチング結果のみをBが最初に受けた取り調べにおいて取調室で目撃したということもありえますよね。
Bにとっては、
（0）→１
のように見えるわけです。このときにはBはなにもできないし、Cもなにもできないし、AはBが何かをすることを待機してしまいますよね。デッドロックです。
また例えば、
上記デッドロックを回避するために、Aは、
Aの作業：（0）→１→0→１→0→１→0→１
など、十分な長さでドラミングをするものとしましょう。これでも、Cが先に
１→0→１→0→１を検知してしまうかもしれません。
これでも大丈夫なようにできているのでしょうか？雑談
わお！
-
@Hannibalさん
説明が悪いpekori
B,Cに順序性があるようにかいてしまいました
Aのハートビート上の異なるBIT列101、10101の検出でいけると書こうとしたのですが、説明が滅茶苦茶。一時保留させて貰って考え直します。追記：23：40
A:１０１０・・・・のハートビート
B、C：１0１検出で0付加＜１位相進行＞
A、1位相進行の検出回数カウント
これで如何でしょう昨日話題に取り上げたBeckwithさんですが、
テキスト構造の伝搬：大乗仏教の論書⇒イスラム法学・神学テキスト⇒スコラ哲学者テキスト
高等教育システムの伝搬：vihāra⇒ madrasa⇒college,
以上の仮説をテーマにwarrior of the cloistersと言う著書もあり、初期イスラム関係文献の薮たたきで高句麗語についての著書も発見しました
並行して読んでいるので大変(;'∀')
-
@riffraff さん
互いに素でないのは不思議でしたがそれは私が徹底的に不馴れなのかもしれません。
私の観点では誰か二人が情報のやりとりをしている間は他の者たちにとってその伝送経路はビジーでなければなりません。
-
@Hannibal さん
回路での説明を考えてみます。＜間違いに気づくかも？＞情報伝達はHeart beat Drummerへの片方向ですし、Followersの尋問完了報告が排他制御されていれば、Tokenの衝突は起こらないと考えます。
明日は早朝から外出ですので、ここまでとします。
次は明日深夜になると思います
-
@riffraff さん
初期状態における明滅が不明で囚人が３人の場合には恐るべき簡単解がありました。
いやあ失敗失敗。４人にすればよかった……ドラマーは叩かない解…
簡単解
３人だと、電球オンオフの２進の２に１を加えたものが３なので簡単解が成立します。
A:宣言者
B:報告者０
C:報告者１とし、３人の事前の取り決めを以下のようにする。
①Aは電球スイッチに手を触れない。
②Bは取り調べられたときに電球がオンのときにのみ毎回オフにする。電球がオフのときには電球スイッチに手を触れない。
つまり、B=報告者０が取り調べ室を出た直後には電球はオフになっている。③Cは取り調べられたときに電球がオフのときにのみ毎回オンにする。電球がオンのときには電球スイッチに手を触れない。
つまり、C=報告者１が取り調べ室を出た直後には電球はオンになっている。④Aは自分が取り調べられたときの電球のオンオフの状態を毎回記録する。たとえば0と1とでよい。記録のつど数列がどんどん伸びていく。
その数列のなかに、0→1となる変化があればそれは報告者１が取り調べられた証しであり、1→0となる変化があればそれは報告者０が取り調べられた証しである。ふたつの証しを見いだし次第宣言をすればよい。これだと BUSYもくそもないですね… orz
というわけで初期状態における明滅が不明バージョンでは囚人を４名にグレードアップしましょう！！
-
あっ、追記を今読みました。
@riffraff さん、これだけではちょっと難しいかもしれませんね……
RE；追記：23：40
＞A:１０１０・・・・のハートビート
B、C：１0１検出で0付加＜１位相進行＞
A、1位相進行の検出回数カウント
これで如何でしょう⇒
まず、BやCは、何回でも、１0１を検出する都度に、0 を付加していくのかどうかが気になります。
仮にそうであるならば、
Bが2回0 を付加する間に、Cが１度も取り調べを受けていない状態と、BとCとの２人が1回づつ取調べを受けてそれぞれが0を付加した状態との区別を、Aは確率1で知る術はないことと思います。
これを回避するためにプロトコルのちょっとした改造を試みることは可能と思います。
宜しくお願いいたします。
-
@riffraff さんによる、最初の御回答には不備がありますので、その場所のみ念のために記しておきます。
RE；しじふの点灯士
【以下にまず原回答を再掲いたします。】
･２3人中１名を点灯士に任命します
点灯士のお仕事：①電灯が消えていれば点灯②点灯回数をカウント・記憶･残りの２２人を滅灯人と呼びます
滅灯人の役目：①尋問に出頭時、電灯が消えている事態に最初に遭遇した際にのみ滅灯･23回の点灯を行った後、おもむろに”全員漏れなく尋問しましたね”、と答える
【目についた修正要点を次にピックアップしておきます。】
《Ａ》「滅灯人の役目：①」で、消えている電球を更に消すことになっています。
《Ｂ》「･23回の点灯を行った後、おもむろに”全員漏れなく尋問しましたね”、と答える」というのを、最初私は「滅灯人の役目」欄に書かれているものと思い込みました。
-
-
@Hannibal さん
帰宅いたしました
ご指摘了解です
Tokenの提供・占有・開放をうまく説明することを考えます
※しじふの点灯人の件も了解です※主流ではありませんが、カールグレン以来、西欧の言語学者には原始中国語：屈折語（印欧語）説を唱える学派があります。
ベックウィズ以外にも「馬・車輪・言語」のアンソニーなども挙げられます。
-
消灯状態0 点灯状態１とします
A 計算者＜Heart Beat Drummer>
Bi 報告者i初期状態 消灯状態
＜しじふの点灯人改＞
A 消灯状態0⇒点灯状態１
Bi 最初に点灯状態に遭遇した時にのみ消灯状態に1→0
消灯状態、点灯状態遭遇２度目以降、は何もしない
A 消灯状態0⇒点灯状態１X23回で全員尋問完了＜しじふの消灯人＞
Bi 最初に消灯状態に遭遇した時にのみ点灯状態に0→１
点灯状態、消灯状態遭遇２度目以降、は何もしない
A 点灯状態１⇒消灯状態0ｘ22回で全員尋問完了予備的考察
＜しじふの点灯人＞ 点灯状態１ Toke開放
消灯状態０ Token占有
＜しじふの消灯人 消灯状態０ Token開放
点灯状態１ Token占有A 計算者＜Heart Beat Drummer>の制御によりToke開放が行われ
報告者iの操作（点滅）によりToken占有が成立し、以後計算者＜Heart Beat Drummer>の点滅１動作によってToke開放が行えれば良い
初期状態が解っている場合は直前１BitでTokenの状態が判明初期状態不明
（解答例１）
A 最初の３尋問で（0→）１→0→１
Bi 直前３回の状況１→0→１に最初に遭遇した際に消灯1→０
A ＜４回目以降＞0ならば0→１、１の場合は何もしない。
0→１X２２回で全員の尋問完了Token
１→0→１がToken開放
0がToken占有ですいかがでしょうか(;'∀')
-
おお！！
@riffraff さん！！
本日はまず、取調べ室の電球が初期状態でオフであることを囚人たちが知っている場合についての回答例をば開示いたします。
本質的に @riffraff さんによる解と一致しています（と思います）。
回答例【初期にて消灯確定が公知】
初期にて消灯点灯不明の場合と比較するため、都合により初期にて消灯確定が公知の場合も囚人４人の例で示します。（ロジックは２３人でも１００人でも同じです。）
（ア）のちに述べる二通りの役割分担により、消灯人１名と点灯人３名とを任命します。
（イ）全ての囚人が取調べを受けたと宣言するのは消灯人（１名）のみです。（ウ）点灯人の役割を説明します。
点灯人が、電球が消えている部屋に初めて入るときには、点灯します。それ以外の場合には、何もしません。（エ）消灯人の役割を説明します。
消灯人が取調べ室に入るときに電球が消えていれば、何もしません。取調べ室に入るときに電球が点いていれば、消灯します。
消灯するのが３回目であれば、消灯人はすべての囚人が取調べを受けたと宣言します。ここまでの（ア）（イ）（ウ）（エ）の段取りに従えば確率１で囚人たちは釈放されます。
ここであらためて、上のプロトコルでうまくいっている理由をエセ通信用語を使って検証という遊びを試みます。うまく行きますでしょうか。
目的は、各点灯人が１回だけ自分が取調べを受けた旨を消灯人に確実に伝えることです。消灯人は点灯人のうち誰から連絡を受けたかは知らないままで構いません。点灯人のうちの１人が取り調べを受けた旨を連絡してきた、このことを確実に知る、こうした流れが３回おきれば良いです。そのためには１人の点灯人からの情報伝達が他の点灯人からの情報伝達によって破壊されないようにすれば十分です。
各点灯人は他の点灯人からの消灯人への情報伝達が完了（＝消灯人による受領を点灯人が確認）するまで何もしてはいけません。点灯人にとって取調べ室に入る行動は、制御コードでいうところの ENQ すなわち、「(今からデータを送っても)大丈夫？」のような、問い合わせ用のコードを発信することに相当します。実際にはコードの発信を点灯人はしませんし、既にENQに対する消灯人からの応答が取調べ室の電球に於いて示され済みなのです。
すなわち、点灯状態を見たならば NAK；「NG」「だめです」のような、消灯人からの否定の応答を示されているものとし、データを送るなど何もせずに取調べ室を出ます。
また、消灯状態を見たならば、
ACK；「OK」「わかりました」のような、消灯人からの肯定の応答を示されているものとし、点灯人自らが取調べを受けたことを示すデータを送る、すなわち、電球をオン、点灯します。おっと、忘れてはいけません。点灯は初回のみです。消灯人からのACKを確認したとしても、自分が既に報告済みであるならば、他の点灯人にこのACKを譲り渡すこととなります。一方、消灯人の行動を検証します。
消灯人は、電球が点灯していることを見たならば、それは、誰かはわからないけれども特定の１人の点灯人からの只１回の「取り調べを受けました」との情報伝達であると理解します。その旨を記録し、消灯します。これは ACK の意味であり、「次のデータを送ってきてくれたまえ」の信号となります。
消灯人が ACK を送らない限り、点灯人たちにとって、電球のステータスは NAK となっています。以上です。
部屋の電球の初期状態が不明であっても、上のプロトコルはほぼそのまま使えます。若干修正しますが。
