囚人さんのオンオフ



  • この囚人さんのオンオフのスターター問題について、

    ある囚人が取調べ室に入ったときに電球がオンだったとします。このときにこの囚人さんが、どの囚人さんにより電球をオンにされたかについて確実に知るための事前取り決めがあるわけですね。

    ただし、その取り決めが有効になるひとつの条件は、1日につき1回しか取り調べが行われず、また、取調べが行われない日がなく、また、取調べを受ける囚人の決定については物理乱数によるものとしたときと思われます。

    この抜け道を禁止するためには、スターター問題において、下記の設定を追加すればよいことになります。

    囚人が独房に帰ると看守が囚人に全身麻酔をかけて気絶させます。次に取調べが行われる際に麻酔が解かれます。麻酔がかけられていた時間については囚人たちには全くわかりません。

    この追加設定は、眠り姫問題の設定からのパクりです。



  • @Hannibal さん
    私がはまっているのかもしれません。ゆっくり再考してみます。



  • 私の説明が悪いのです。もうすこし解り易い説明と図解を考え中です。
    しばしお待ちを(;'∀')



  • ものわかりが悪くてすみません。



  • 考え始めは、自由に毎回スィッチを作動させれば(Off)-On-Off-On…
    これになあんらかの制限を付ければどうにか出来ないか。でした

    無理やり

    0_1583506869883_seq1.png
    0_1583506941497_seq2.png
    そこで各人基本1アクセス。Off-On-Offを検知したものだけ2回目のアクセス
    2回目のアクセスを行ったものがOff-Onを検知すればOK
    i.e.(図C)+図Cの❸と❹の間で❶が尋問を受けている
    一定期間で検知できなければ再試行

    ここまで書いて2つの事に、はたと気が付きました

    私は馬鹿間抜けorz

    イ。シグナル操作による再試行のトリガーは無理、一定期間をあらかじめ<EX10日>決定しておくことが必要。
    ロ。図1再掲

    0_1583507562269_seq1.png
    全員1試行1アクセス
    On-Off操作を行ったもの(❷&❹)がOn-Offを検知できればOK
    出来なければ、一定期間後再試行でいけます。
    ※もちろん可能性があるのは❷だけですが、被尋問者は自分が❷か❹かわかりません。



  • ↑の2番目の方法が行けるとすると

    完了までの日数の期待値は、人数N、インターバルCとすると
    ❘(N-2)/2|!XC  すこし人数が多くなると!(^^)!



  • ありがとうございます。

    図解だけ見ています。

    テキストのほうが何故か一部の文字がナカグロになっていて…

    ナカグロ

    ※もちろん可能性があるのはナカグロだけですが、被尋問者は自分がナカグロかナカグロかわかりません。

    ナカグロ2

    ナカグロ(N-2)/2|!XC



  • @Hannibal さん

    ローマ数字の部分が白抜き文字(ナカグロです)

    ナカグロ1

    <原文>
    全員1試行1アクセス
    On-Off操作を行ったもの(❷&❹)がOn-Offを検知できればOK
    出来なければ、一定期間後再試行でいけます。
    ※もちろん可能性があるのは❷だけですが、被尋問者は自分が❷か❹かわかりません。
    <変更>
    全員1試行1アクセス
    On-Off操作を行ったもの(Ⅱ&Ⅳ)がOn-Offを検知できればOK
    出来なければ、一定期間後再試行でいけます。
    ※もちろん可能性があるのはⅡだけですが、被尋問者は自分がⅡかⅣかわかりません。

    ナカグロ2

    エクセルの関数形にします
    Fact{Round((n-2)/2)}*C
    <修正23:15>



  • @riffraff さん

    文字のご解説をまことにありがとうございます。

    質問があります。多数フェーズからなるわけですが、各人にとってみかけ上の累積フェーズ数は確率1で一致していますでしょうか。

    私が囚人だとして、私がフェーズ1にちょっと参加した後フェーズ1がまだ続いている気がしている、そんななか私が暫く取り調べが行われなかったときに、他のメンバーがフェーズをいくつか進めていたかもしれないしそうではないかもしれない、それらのことを確率1で峻別しなくても大丈夫なのかしらと頭をひねり続けているのです。



  • @Hannibal さん
    今回の解では以下の条件を想定しています
    ①囚人の生命は無限
    ②エラーフリーの記憶
    その上で各囚人の責務は
    ❶一定期間中に所定のON・OFFパターンを検知できれば完了報告
    ❷一定期間完了後、次フェーズ❶へ
    以下ループです。囚人はパターン検知機器であり、検知/非検知の二価の何れかを取ります。
    ご質問に答えたことになるのでしょうか。

    ※信号でフェーズを区切れないかとも考えましたが・・・
     窮余の一策としてタイマーリセットを導入しました



  • @riffraff さん

    反例探しに疲れました… これだけ探索してみつからないのでたぶんうまくいっているのですね(≧∇≦)

    直感的にはうまくいきそうにない気がしてましたし未だに腑に落ちないので悔しいです。
    (o⌒∇⌒o)

    少し何もしないで放置し、脳みそをリセットしていずれまた取り組んでみたい気が満々です。
    そしたらツボを理解するかめですし。
    くはあ



  • @Hannibal さん
    ある種トリビアルな解だと思っていますが、私自身100%腑に落ちている訳ではありません。
    一意的な解と言う縛りを外した故かとも思っています。


Log in to reply
 

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