囚人さんのオンオフ



  • <ため息さんちでのハンニバル・フォーチュンさん出題パズル>
     {一部文字レベルで修正}
    23人の囚人のグループが刑務所の食堂に集められて、次のように言われる。これから全員がそれぞれ独房に入れられたのち、スイッチつきの電球がひとつだけある部屋で一人ずつ取調べを行う。囚人たちはその電球を点灯または消灯することであとから入ってくる囚人とやりとりしてもよい(そして、それだけがやりとりをする唯一の手段でもある)。電球の明かりは部屋の外に漏れない。最初、電球は消えている。取調べは決められた順序で行われるものではなく、取調べの間隔も決まっておらず、どの時点においても、それまでに何度か取調べを受けた囚人がまた取調べを受けるかもしれない。囚人は取調べを受けるとき、電球のスイッチをそのままにしておくか、あるいは点灯・消灯させることができる。
    囚人の誰かが取調べを受けるときに、23人の囚人全員がすでに取調べを受けたと宣言することが目標である。(その宣言は無理に行わなくてもよい)。その宣言が正しければ、囚人は全員釈放されるが、間違っていれば、全員が処刑される。独房にはいる前に食堂に集められた囚人たちは、(この場限りで互いに相談しておくことが許されているが、)自分たちが釈放されるような事前の取り決めを交わしておくことができるだろうか。

    以上、名著「100人の囚人と1個の電球」から引用しました。


  • System

    先頭記事が更新されました。



  • @riffraff 自己レス
    <雑談コーナーでの澪標書き込み>
    各人に点滅回数に対応した一意の「ばいなりーこーど」を付与しこれに従って行動。<尋問時に自分に付与されtコードに遭遇した際に、点滅を逆にし、それ以外のケースはなにもしない。>

    上記初等解の図

    0_1581649486345_P-B.jpg



  • @riffraff 自己レス

    これだめです。自爆!(^^)!



  • 超お馬鹿な解を発見!(^^)!

    しじふの点灯士

    ❶23人中1名を点灯士に任命します
    点灯士のお仕事:①電灯が消えていれば点灯②点灯回数をカウント・記憶
    ❷残りの22人を滅灯人と呼びます
    滅灯人の役目:①尋問に出頭時、電灯が消えている事態に最初に遭遇した際にのみ滅灯
    ❸23回の点灯を行った後、おもむろに”全員漏れなく尋問しましたね”、と答える

    あまりにお馬鹿です。(;'∀')



  • 惜しい!

    実に惜しいです!
    ①最初、電球は消えているんです。

    ②《滅灯人の役目:①尋問に出頭時、電灯が消えている事態に最初に遭遇した際にのみ滅灯

    いや、滅灯時に滅灯できません。



  • 「100人の囚人と1個の電球」では、バリエーションとして、《取調室の電球のオンオフの状態を、囚人たちは事前の合議の段階では知らない》という問題をも解説しています。

    囚人が3人の場合で結構ですので……



  • @Hannibal さん

    問題読み違えではありません!(^^)!

    点灯士のお仕事:①電灯が消えていれば点灯・・・以下略

    しじふの消灯士(謎)にくらべれば半手間増えますので、最短候補ではありませんね(;'∀')

    追加問題考えてみます。

    これからの続きはこのスレッドにします。雑談コーナーでは先ほどの書き込みを最後とします。

    話は変わりますが、Christopher Beckwithと言う中央ユーラシアの言語・歴史学者がいます。博覧強記というかHomo Unibersalisとでも呼ぶべきかたですが、その方の高句麗語に係る著作<
    Koguryo, the Language of Japan's Continental Relatives>をひょんなことから入手しました。読み始めた所ですが面白い。ベースになる中古中国音の復元が、カールグレン以来の方法とも日本中国学の方法とも異なる、同時代並行言語(チベット語等)をベースにしていいます。(まだ流し読み始めたばかりですので、その妥当性についてはなんともいえませんが刺激的です。)



  • @Hannibalさん
    明滅不明問題:
    ますます通信工学の問題に見えてきました。
    3人のケースを書きます

    オマジナイ

    A ドラマー
    B フォロワー1
    C フォロワー2
    消灯状態0 点灯状態1とします
    Aの作業:(0)→1→0→1
    Bの作業:<1→0→1>を検知して1→0
    Aの作業:0→1→0→1→0→1
    Cの作業:1→0→1→0→1を検知して1→0
    全体としては
    (0)→1→0→1→0→1→0→1→0→1→0
    又は(0)→1→0→1→0→1→0
    又は(0)→1→0→1→0→1→0→1→0

    クロック制御に信号を織り込む方式を思い出しました

    雑談

    もう一つ思い出したのは暗号史上の都市伝説
    ポーランドの通信士がドイツ第三帝国の公用通信にパルチザン間の情報連絡をハートビートや確認エンヴェロープにまぎれこませた。



  • @riffraff さん

    明滅不明問題3人のケースの御回答について書きます。

    RE:オマジナイ

    A ドラマー
    B フォロワー1
    C フォロワー2
    消灯状態0 点灯状態1とします
    Aの作業:(0)→1→0→1
    Bの作業:<1→0→1>を検知して1→0

    ==

    確認したいのですが、思うに、
    本解の意図としては、Bの作業よりも先にCの作業が行われないようにしたプロトコルなのですよね?

    そのことを前提にお尋ねいたします。

    取調べが行われる順番はランダムですので、

    Aの作業:(0)→1→0→1

    の各段階の全てをCのみが知っていて、Bは知らないこともあろうかとは思うのです。

    たとえば、Bは、
    Aが三回取り調べを受けた局面で、つまり
    (0)→1→0→1
    において
    一回目のスイッチングと二回目のスイッチングが行われたことを知らないでいて、三回目のスイッチング結果のみをBが最初に受けた取り調べにおいて取調室で目撃したということもありえますよね。
    Bにとっては、
    (0)→1
    のように見えるわけです。

    このときにはBはなにもできないし、Cもなにもできないし、AはBが何かをすることを待機してしまいますよね。デッドロックです。

    また例えば、
    上記デッドロックを回避するために、Aは、
    Aの作業:(0)→1→0→1→0→1→0→1
    など、十分な長さでドラミングをするものとしましょう。

    これでも、Cが先に
    1→0→1→0→1を検知してしまうかもしれません。
    これでも大丈夫なようにできているのでしょうか?

    雑談

    わお!



  • @Hannibalさん

    説明が悪いpekori

    B,Cに順序性があるようにかいてしまいました
    Aのハートビート上の異なるBIT列101、10101の検出でいけると書こうとしたのですが、説明が滅茶苦茶。一時保留させて貰って考え直します。

    追記:23:40
    A:1010・・・・のハートビート
    B、C:101検出で0付加<1位相進行>
    A、1位相進行の検出回数カウント
    これで如何でしょう

    昨日話題に取り上げたBeckwithさんですが、
    テキスト構造の伝搬:大乗仏教の論書⇒イスラム法学・神学テキスト⇒スコラ哲学者テキスト
    高等教育システムの伝搬:vihāra⇒ madrasa⇒college,
    以上の仮説をテーマにwarrior of the cloistersと言う著書もあり、初期イスラム関係文献の薮たたきで高句麗語についての著書も発見しました
    並行して読んでいるので大変(;'∀')



  • @riffraff さん

    互いに素でないのは不思議でしたがそれは私が徹底的に不馴れなのかもしれません。

    私の観点では誰か二人が情報のやりとりをしている間は他の者たちにとってその伝送経路はビジーでなければなりません。



  • @Hannibal さん
    回路での説明を考えてみます。<間違いに気づくかも?>

    情報伝達はHeart beat Drummerへの片方向ですし、Followersの尋問完了報告が排他制御されていれば、Tokenの衝突は起こらないと考えます。

    明日は早朝から外出ですので、ここまでとします。
    次は明日深夜になると思います



  • @riffraff さん

    初期状態における明滅が不明で囚人が3人の場合には恐るべき簡単解がありました。
    いやあ失敗失敗。4人にすればよかった……

    ドラマーは叩かない解…

    簡単解

    3人だと、電球オンオフの2進の2に1を加えたものが3なので簡単解が成立します。

    A:宣言者
    B:報告者0
    C:報告者1

    とし、3人の事前の取り決めを以下のようにする。

    ①Aは電球スイッチに手を触れない。

    ②Bは取り調べられたときに電球がオンのときにのみ毎回オフにする。電球がオフのときには電球スイッチに手を触れない。
    つまり、B=報告者0が取り調べ室を出た直後には電球はオフになっている。

    ③Cは取り調べられたときに電球がオフのときにのみ毎回オンにする。電球がオンのときには電球スイッチに手を触れない。
    つまり、C=報告者1が取り調べ室を出た直後には電球はオンになっている。

    ④Aは自分が取り調べられたときの電球のオンオフの状態を毎回記録する。たとえば0と1とでよい。記録のつど数列がどんどん伸びていく。
    その数列のなかに、0→1となる変化があればそれは報告者1が取り調べられた証しであり、1→0となる変化があればそれは報告者0が取り調べられた証しである。ふたつの証しを見いだし次第宣言をすればよい。

    これだと BUSYもくそもないですね… orz

    というわけで初期状態における明滅が不明バージョンでは囚人を4名にグレードアップしましょう!!



  • あっ、追記を今読みました。

    @riffraff さん、これだけではちょっと難しいかもしれませんね……

    RE;追記:23:40

    >A:1010・・・・のハートビート
    B、C:101検出で0付加<1位相進行>
    A、1位相進行の検出回数カウント
    これで如何でしょう

    まず、BやCは、何回でも、101を検出する都度に、0 を付加していくのかどうかが気になります。

    仮にそうであるならば、

    Bが2回0 を付加する間に、Cが1度も取り調べを受けていない状態と、BとCとの2人が1回づつ取調べを受けてそれぞれが0を付加した状態との区別を、Aは確率1で知る術はないことと思います。

    これを回避するためにプロトコルのちょっとした改造を試みることは可能と思います。

    宜しくお願いいたします。



  • @riffraff さんによる、最初の御回答には不備がありますので、その場所のみ念のために記しておきます。

    RE;しじふの点灯士

    【以下にまず原回答を再掲いたします。】

    ・23人中1名を点灯士に任命します
    点灯士のお仕事:①電灯が消えていれば点灯②点灯回数をカウント・記憶

    ・残りの22人を滅灯人と呼びます
    滅灯人の役目:①尋問に出頭時、電灯が消えている事態に最初に遭遇した際にのみ滅灯

    ・23回の点灯を行った後、おもむろに”全員漏れなく尋問しましたね”、と答える

    【目についた修正要点を次にピックアップしておきます。】

    《A》「滅灯人の役目:①」で、消えている電球を更に消すことになっています。

    《B》「・23回の点灯を行った後、おもむろに”全員漏れなく尋問しましたね”、と答える」というのを、最初私は「滅灯人の役目」欄に書かれているものと思い込みました。



  • @riffraff さん

    ベックウィズは「シナ・チベット語族の存在を認めない」と Wikipedia にあって腰を抜かしました。

    ううむ。



  • @Hannibal さん
    帰宅いたしました
    ご指摘了解です
    Tokenの提供・占有・開放をうまく説明することを考えます
    ※しじふの点灯人の件も了解です

    ※主流ではありませんが、カールグレン以来、西欧の言語学者には原始中国語:屈折語(印欧語)説を唱える学派があります。
    ベックウィズ以外にも「馬・車輪・言語」のアンソニーなども挙げられます。



  • 消灯状態0 点灯状態1とします
    A 計算者<Heart Beat Drummer>
    Bi 報告者i

    初期状態 消灯状態

    <しじふの点灯人改>
    A 消灯状態0⇒点灯状態1
    Bi 最初に点灯状態に遭遇した時にのみ消灯状態に1→0
      消灯状態、点灯状態遭遇2度目以降、は何もしない
    A 消灯状態0⇒点灯状態1X23回で全員尋問完了

    <しじふの消灯人>
    Bi 最初に消灯状態に遭遇した時にのみ点灯状態に0→1
      点灯状態、消灯状態遭遇2度目以降、は何もしない
    A 点灯状態1⇒消灯状態0x22回で全員尋問完了

    予備的考察

    <しじふの点灯人> 点灯状態1 Toke開放
              消灯状態0 Token占有
    <しじふの消灯人  消灯状態0 Token開放
              点灯状態1 Token占有

    A 計算者<Heart Beat Drummer>の制御によりToke開放が行われ
      報告者iの操作(点滅)によりToken占有が成立し、以後計算者<Heart Beat Drummer>の点滅1動作によってToke開放が行えれば良い
     初期状態が解っている場合は直前1BitでTokenの状態が判明

    初期状態不明

    (解答例1)
    A 最初の3尋問で(0→)1→0→1
    Bi 直前3回の状況1→0→1に最初に遭遇した際に消灯1→0
    A <4回目以降>0ならば0→1、1の場合は何もしない。
     0→1X22回で全員の尋問完了

    Token

    1→0→1がToken開放
    0がToken占有です

    いかがでしょうか(;'∀')



  • おお!!

    @riffraff さん!!

    本日はまず、取調べ室の電球が初期状態でオフであることを囚人たちが知っている場合についての回答例をば開示いたします。

    本質的に @riffraff さんによる解と一致しています(と思います)。

    回答例【初期にて消灯確定が公知】

    初期にて消灯点灯不明の場合と比較するため、都合により初期にて消灯確定が公知の場合も囚人4人の例で示します。(ロジックは23人でも100人でも同じです。)

    (ア)のちに述べる二通りの役割分担により、消灯人1名と点灯人3名とを任命します。
    (イ)全ての囚人が取調べを受けたと宣言するのは消灯人(1名)のみです。

    (ウ)点灯人の役割を説明します。
    点灯人が、電球が消えている部屋に初めて入るときには、点灯します。それ以外の場合には、何もしません。

    (エ)消灯人の役割を説明します。
    消灯人が取調べ室に入るときに電球が消えていれば、何もしません。取調べ室に入るときに電球が点いていれば、消灯します。
    消灯するのが3回目であれば、消灯人はすべての囚人が取調べを受けたと宣言します。

    ここまでの(ア)(イ)(ウ)(エ)の段取りに従えば確率1で囚人たちは釈放されます。

    ここであらためて、上のプロトコルでうまくいっている理由をエセ通信用語を使って検証という遊びを試みます。うまく行きますでしょうか。

    目的は、各点灯人が1回だけ自分が取調べを受けた旨を消灯人に確実に伝えることです。消灯人は点灯人のうち誰から連絡を受けたかは知らないままで構いません。点灯人のうちの1人が取り調べを受けた旨を連絡してきた、このことを確実に知る、こうした流れが3回おきれば良いです。そのためには1人の点灯人からの情報伝達が他の点灯人からの情報伝達によって破壊されないようにすれば十分です。
    各点灯人は他の点灯人からの消灯人への情報伝達が完了(=消灯人による受領を点灯人が確認)するまで何もしてはいけません。

    点灯人にとって取調べ室に入る行動は、制御コードでいうところの ENQ すなわち、「(今からデータを送っても)大丈夫?」のような、問い合わせ用のコードを発信することに相当します。実際にはコードの発信を点灯人はしませんし、既にENQに対する消灯人からの応答が取調べ室の電球に於いて示され済みなのです。
    すなわち、点灯状態を見たならば NAK;「NG」「だめです」のような、消灯人からの否定の応答を示されているものとし、データを送るなど何もせずに取調べ室を出ます。
    また、消灯状態を見たならば、
    ACK;「OK」「わかりました」のような、消灯人からの肯定の応答を示されているものとし、点灯人自らが取調べを受けたことを示すデータを送る、すなわち、電球をオン、点灯します。おっと、忘れてはいけません。点灯は初回のみです。消灯人からのACKを確認したとしても、自分が既に報告済みであるならば、他の点灯人にこのACKを譲り渡すこととなります。

    一方、消灯人の行動を検証します。
    消灯人は、電球が点灯していることを見たならば、それは、誰かはわからないけれども特定の1人の点灯人からの只1回の「取り調べを受けました」との情報伝達であると理解します。その旨を記録し、消灯します。これは ACK の意味であり、「次のデータを送ってきてくれたまえ」の信号となります。
    消灯人が ACK を送らない限り、点灯人たちにとって、電球のステータスは NAK となっています。

    以上です。

    部屋の電球の初期状態が不明であっても、上のプロトコルはほぼそのまま使えます。若干修正しますが。


Log in to reply
 

Looks like your connection to パズルハウス was lost, please wait while we try to reconnect.