面白い数学の問題おしえて～な 41問目
■ このスレッドは過去ログ倉庫に格納されています
面白い数学の問題を紹介して解き合うスレです
質問スレではありません
出題者が答えを知らない問題はお控えください
統計学などはスレ違い、数学以外の話題は論外です
荒らし、煽りはスルー推奨
前スレ
面白い数学の問題おしえて～な 40問目
https://rio2016.5ch.net/test/read.cgi/math/1640443648/
過去ログ(1-16問目)
http://www3.tokai.or.jp/meta/gokudo-/omoshi-log/
まとめwiki
http://w.atwiki.jp/omoshiro2ch/ さすがに難しいと思うのでもう少しヒント
・各フェーズは毎回同じターン数（≒情報量）である必要は無い。
・797で言及した悪魔の戦略は、個人的にはルータ戦略と呼んでる。（情報を中継しているだけという意味を込めて）
幼女0,2間の信頼関係を永遠に断つには、悪魔は
幼女0から受ける伝達内容を全く同じ内容かつタイミングで幼女2に送り、
幼女2から受ける伝達内容を全く同じ内容かつタイミングで幼女0に送れば良い。
あるタイミングで３つ同時押しする必要はあるが、あるフェーズで幼女2への伝達内容を幼女1,3にも同時に送れば良い。
そうすると幼女1,3には悪魔であることがバレるが、幼女0,2は依然としてどちらが本物かはわからない。 >>799
読み間違ってるよ
いくつかの信頼出来るチャネルを通じて情報を伝える事ができるときnはmを信頼出来ると表すとする、
って書いてるやん？
幼女1が幼女0を信頼してるというのは幼女0から幼女1へ開いてるチャネルが直接信頼出来る必要はない
幼女0から幼女2へのチャネルが信頼でき、幼女2から幼女1へのチャネルが信頼できる場合も幼女0は幼女1へ自分が持ってる情報を幼女1へ“幼女0からの信頼出来る情報”として送信できる
だからわざわざ
“いくつかの信頼出来るチャネルを通じて”
って書いてるやん？ >>790-796
なーーるほど……開始フェーズと非0制約を設けることで３人チームになった時にうまいことはたらいてくれるのか、うまいな
「直接ではなくとも便りが来る」という発想が自分にはできなかったわ
お見事、正解です
想定解はガッチガチにプロトコル決めて証明する流れだったけど、
どうせ証明に必要になった情報を載せる方法は後からいくらでも考えられるよな…って気づいてからわりとどうでも良くなったしまあいいや
お疲れ様でした >>803
そうそう、この“最初に自分をたたき起こしたボタンに番号0を割り振る”で番号0を葬り去るのかこの作戦のミソ
この問題で最初に考えたのはとりあえず「自分が信頼できない高々２つのボタンを一斉に押す」だけどこれはうまくいかない
例えば悪魔が幼女0,1,2に幼女3のフリしてチャネルを開いた場合、幼女0,1,2は悪魔部屋と幼女3へのボタンを全部押してしまうので、悪魔も死ぬけど幼女3も死んでしまう
コレを避けるにはどうするか、この状況で偽幼女3をどうやって見破るかがメイン
もちろん“3ボタン同時押下ルール”を使うわけだけど、そこで各チャネルに番号を振るアイデアが出てくるけどそれだけだとうまくいかない、前の方に書いた判定不能の例が出てきてしまう、番号のわり振り方が0,1,2,3自由にできてしまうとうまくいかない
そこで“番号0のチャネルを悪魔に押し付ける作戦”を思いついて解決
中々楽しかったです 想定解のプロトコル
最初のチャイムが鳴り終わってから4^4分間を1ラウンド目、(n-1)ラウンド目が終わってから4^(4^n)分間をnラウンド目とする。
各幼女は各ラウンドで4進法表記の4^n桁の整数Mでメッセージを伝えるために、各ラウンド開始後(M+1)回目のチャイムが鳴った直後に一回だけ相手のボタンを光らせる。
メッセージMは以下の構成とする。
Mは1桁のヘッダ、4^n-3桁の本文、2桁のフッタをこの順で並べたものとする。
ヘッダは自分を表す番号とする。（幼女iならiということ）
n=1の時の本文は3とする。
n>1の時の本文は、自分以外の幼女の番号を小さい順にp,q,rと並べた時に、
幼女pである可能性を排除できないボタンからのn-1ラウンド目の本文とフッタ（4^(n-1)-1桁）、
幼女qである可能性を排除できないボタンからのn-1ラウンド目の本文とフッタ（4^(n-1)-1桁）、
幼女rである可能性を排除できないボタンからのn-1ラウンド目の本文とフッタ（4^(n-1)-1桁）、
悪魔である可能性を排除できないボタンからのn-1ラウンド目のメッセージ全文（ただし悪魔と確定していたらヘッダは自身の番号、他は全て0で埋める）（4^(n-1)桁）
をこの順で並べたものとする。
これによりヘッダと本文は、同じ幼女からは全員に同じものが送られることが保証される。
フッタは、信頼状態とラベルをこの順で並べたものとする。
信頼状態とは、下記の意味を持つ一桁の整数とする。
3：このメッセージの送り先が誰なのか検討もつかない（1ラウンド目のみで使う）
2：このメッセージの送り先が特定の幼女か悪魔かまで絞れた
1：このメッセージの送り先が確定した
0：直接的な相互信頼が、自分と他の幼女全ての間と、自分以外の幼女二組以上の間で存在することを確認したので、次のラウンドが始まったらすぐ、悪魔である可能性が排除できていない全てのボタンを押してください
※幼女pq間の直接的な相互信頼とは、幼女pがqに通じるボタンを確定させ、幼女qがpに通じるボタンを確定させた状態を言う。
ラベルとは、事前に自分の手元にあるボタンに互いに異なるよう振った番号とし、ボタンと番号の対応はゲーム中不変とする。
これによりフッタは、同じ幼女からは全員に異なるものが送られることが保証される。 証明のポイントは下記の補題
・直接的な信頼のチェーンp→q→r→pが生じたらその後３ラウンド以内にp→r→q→pも生じる
・p→q→r→s→pが生じたらその後４ラウンド以内にp→s→r→q→pも生じる
・悪魔が勝つためには誰からも信頼されない幼女（つまり大きさ1,3のチーム）を作らなければならない
あとは、悪魔が大きさ3のチームの2人以上に対して全く同じメッセージを送るタイミングで、
大きさ1のチームが発した本文と悪魔が発した本文が同じか異なるかのいずれの場合でもいつか誰かが悪魔を見破ることができるのを示して終わり >>806
厳密に書いてなかったが、直接的な信頼p→qとは幼女pが幼女qに通じるボタンを確定させることを言う。
１つ目の補題の証明
nラウンド目に直接的な信頼 p→q, q→r, r→p（これをp→q→r→pと略記することにする）が生じたとする。
つまり、nラウンド目終了時にrはpを信頼し、かつpがrにどのラベルを付加して送信したかがわかる。
nラウンド目にrがpから受け取ったラベルをLとする。
これより、n+1ラウンド目にqが信頼できるrから受け取る情報には
「nラウンド目で信頼できるpから送られたラベルはLである」
という内容が含まれる。
同様にして、n+2ラウンド目にpが信頼できるqから受け取る情報には
「n+1ラウンド目で信頼できるrから
『nラウンド目で信頼できるpから送られたラベルはLである』
を含む情報が送られた」
が含まれる。
pはこの情報から、ラベルLを付加して情報を送信することにしたボタンの先にrがいることを導けるので、直接的な信頼p→rが生じる。
r→q, q→p が生じることも同様にして導けるので、１つ目の補題は証明された。
２つ目の補題の証明も同様なので省略。 ３つ目の補題の証明
あるラウンドでp→q→r→s→pの直接的な信頼が生じているとすると、２つ目の補題から、その４ラウンド後にはp→s→r→q→pも生じる。
もしゲーム中どこかのタイミングでpが悪魔を特定したら、直接的な信頼p→r、ひいてはp→r→q→pが生じるので、
１つ目の補題から、３ラウンド後にはp→q→r→pも生じる。
つまりその１ラウンド後には、幼女pは自分が他の幼女全員と直接的な相互信頼を結んでいることと、
自分以外の幼女間の直接的相互信頼が少なくとも２組（qr間とrs間）が生じていることを、信頼できるq,r,sから受信したフッタから把握することができる。
よって、次のラウンドでpが信頼状態0を発信することで悪魔を退治することができる。
これは、ゲーム中他の幼女が悪魔を特定した場合も同様なので、悪魔は誰にも自分を特定されてはならない。
そのためにはpにはr、qにはs、rにはp、sにはqであると自分を騙り続ける必要があるが、これは３ボタン同時押しのタイミングで破綻する。
以上から、悪魔は自身が勝つためには、直接的な信頼関係のチェーンp→q→r→s→pを生じさせてはならない。
幼女を頂点、直接的な信頼関係を辺とした有向グラフを考えると、このグラフはどの頂点も２以上の出次数を持たなければならないが、
頂点数が４、各頂点の出次数が２である有向グラフGを分類することで、有向辺のチェーンp→q→r→s→pが存在しないパターンは
特定の頂点の入次数が０であるパターンに限られることがわかる。
（無向グラフ G':= ({p,q,r,s}, {{x,y}: x→y,y→xがどちらもGの辺}) により分類する方法が簡易。）
（３つ目の補題の証明終わり） 任意の格子点(x,y)が4点(x+|y|+1,y),(x-|y|-1,y),(x,y+|x|+1),(x,y-|x|-1)と結ばれている。
同じ点を２回通らずに元の点に戻ってこれる点は存在するか？ 結んでる線分同士公差しまくってるやん
乗り換えありならいくらでも戻ってこれるやろ >>809
全く分からんorz
例えば
幼女0の部屋は左から順に123ア
幼女1の部屋は左から順に023ア
幼女2の部屋は左から順に013ア
幼女3の部屋は左から順に012ア
とつながってるとして悪魔は幼女012には3、幼女3には0を名乗ってるとします
どうなったら見破れるんですか？ (0,0),(1,0),(0,0).
(0,0),(1,0),(1,2),(-2,2),(-2,-1),(0,-1),(0,0). つまり
0→1,1→0, 0→2,2→0, 1→2,2→0
3→1, 3→2
は自己紹介の時点で確定してるとしてここからどうやって3→0か3→1を決定できるんですか？ 違う
0→3,1→3,2→3のどれか
幼女0,1,2のうち1人でも幼女3を名乗る部屋へのボタンがある
どれか一つでも真贋を見極められれば幼女の勝ち
どんな顛末でそれが確定するんですか？ まだ違う
幼女0,1,2の3人の部屋にはどれも幼女3を名乗る参加者へのボタンを持ってる、左のボタンが正解、どうなったら見抜けるんですか？ すまん、途中で忙しくなって中途半端だったけど >>809 の続き
３つ目の補題より、以降は誰からも信頼されない幼女が生じてしまった場合について考えれば良い。
誰からも信頼されない幼女をpとする。
あるラウンドで、悪魔は３つのボタンを同時に押下する必要があるが、
それはp以外の少なくとも２人の幼女q,rに対して全く同じメッセージが悪魔から送られることを意味する。
nラウンド目に悪魔がq,rに対して送った本文をB, フッタをFとおく。
また、同じラウンドにpがi （i=q,r）に送った本文をb, フッタをfiとおく。
（プロトコルからpがq,rに対して送る本文は同一）
(1) B≠b の時
n+1ラウンド目でq,rは、直前のラウンドで幼女pと名乗る２名から自分に送られた本文とフッタについての情報を交換することになる。
具体的には、qが受け取った本文とフッタの組は(b,fq)と(B,F)、rが受け取った本文とフッタの組は(b,fr)と(B,F)、という情報である。
ここで、同一の本文を送らなければならないというプロトコル上の制約から、Bを送った人とbを送った人を区別することができるが、
Bを送った人が同じフッタを別々の幼女q,rに送ったことがわかるので、プロトコル違反によりq,rは悪魔を特定できる。 (2) B=b の時
n≧2 として良い。
（最初のラウンドで悪魔が幼女pと同じ本文をq,rに同一のフッタで送ったとすると、
次のラウンドで、もしフッタを変えたら即座に悪魔がバレるし、
もしフッタを変えなくとも悪魔がpと異なる本文をq,rに送れば (1) の状況になりいずれ悪魔を特定されるので、
残った考えるべき状況は、２ラウンド目以降で悪魔がpと同じ本文をq,rに送った場合のみである。）
nラウンド目に悪魔とpからq,rに対して送られた本文 b(=B) には、n-1 ラウンド目にpがq,rそれぞれから受け取ったフッタの情報が含まれる。
したがってq,rはどちらも、自分がn-1ラウンド目にどのボタンからどのフッタを送ったかの情報と照合することで、
どのボタンが本当のpに通じるボタンかを特定することができるので、もう片方が悪魔であるとわかる。
以上より、(1)(2)いずれの場合も大きさ3のチームのメンバのうち誰かは悪魔を特定することができる。（証明終わり） >>819
> nラウンド目に悪魔とpからq,rに対して送られた本文 b(=B) には、n-1 ラウンド目にpがq,rそれぞれから受け取ったフッタの情報が含まれる。
この後半は正確には『n-1 ラウンド目でpがq,rのうち信頼した少なくとも一方から受け取ったフッタの情報が含まれる』だな
> したがってq,rはどちらも、
これも『q,rのうちpから直接的に信頼された方は』に修正
要は悪魔がpに対してどのように騙ったとしても、pはq,rのうち少なくとも一方を信用することができる訳だから、
q,rのうち「自分がpから直接的に信頼されてる」とわかった方が悪魔を特定すれば良い、ということ。 >>818
あるラウンドで、悪魔は３つのボタンを同時に押下する必要があるが、
それはp以外の少なくとも２人の幼女q,rに対して全く同じメッセージが悪魔から送られることを意味する。
コレはなんでですか？
この同時3押下ルールが保証してくれるのは
「あるタイミングで２つのメッセージで同時刻に押されているビットが少なくともひとつある」
だけで全文全く同じになる必要はないのではないですか？ >>821
まさにそこが >>805 のプロトコルの便利な所で、
各ラウンドで各幼女が各ボタンをただ一回ずつ押下すると決めることにより、
「各ラウンドが始まってから何回目のチャイムが鳴った後にボタンを押したか」を表す１つの整数に、必要なあらゆる情報を詰め込むことができる。
具体例をあげると、幼女0は1ラウンド目で各ラベル i=0,1,2,3 がついたボタンからメッセージ"033i"を送ることになるから、
1ラウンド目が始まってから 0*4^3 + 3*4^2 + 3*4 + i 回チャイムが鳴った後にラベルiのボタンを一回ずつ押して、1ラウンド目の行動はそれで終わり。
（勿論各ラウンドに複数回光ったボタンがあれば、プロトコル違反なのでそれが悪魔であると導くこともできる。） >>822
情報を2ビットずつ区切って0,1,2,3の信号送るんですよね？
もし全幼女が第1ラウンドで033iを送るなら全幼女は第1ラウンド3ビット目は1を発信する事になります、じゃあこのタイミングで全幼女は全ボタンを全押しするんじゃないですか？
悪魔も全押しすれば全員死にますよ？ >>823
プロトコル見てもらえればわかると思うけど、ヘッダに0をつけられるのは悪魔を除けば幼女0だけよ。
幼女1ならヘッダも1、幼女2ならヘッダも2、幼女3ならヘッダも3ということ。
その後もずっと（信頼できる幼女から信頼状態0が送られるまでは）ヘッダは自分自身の番号だから、複数の幼女からのメッセージが衝突することは無い。 > 情報を2ビットずつ区切って0,1,2,3の信号送るんですよね？
えーともしかして1ラウンド目に幼女0が、例えばラベル1を付加したボタンから"0331"のメッセージを送るために、チャイムが鳴るごとに
「押さない、押さない、押す、押す、押す、押す、押さない、押す」
の順番でボタンを押下することで情報を送信すると思っている？
ならそれは勘違いで、822で例示した通り、このプロトコルに従えば1ラウンド目の行動は
「押さない、押さない、…、押さない、押す、押さない、押さない、…、押さない」
↑序盤に「押さない」が61=0331(4)回続き、「押す」を1回挟んだ後、1ラウンド目終わりまで「押さない」を続ける
となる。これを受け取った方はこれを複合して
「このボタンからは整数61=0331(4)が送られてきたから、自分を幼女0と主張している訳だな」
とわかる。 >>825
なるほど、ビット間の長さで情報送るんですね
ではプロトコルに従う限り何故同一の送信者は同一のタイミングでボタンを押せないんですか？
メッセージの転送開始時点の取り決めが“転送者の自由”ならいくらでも正当なメッセージでも同一の時点で1が発生するようにできるのではないですか？ >>826
何でわざわざ宛先ごとにフッタを変えて送信する必要があるのかということ？
>>818の最後あたりで「同一の送信者から別々の宛先に同じラベルが振られることはない」というプロトコルの性質をもとに違反判定してるから、
答えとしては、このように悪魔判定ができるように、かな
こう決めなくてもうまくいくかどうかは確かめてない あもしかして、「ラウンドの始まりは自由に決めていいなら、光ったタイミングがどの整数を表すかわからないのでは」ということ？
それなら「ラウンドの始まりはプロトコルで厳密に決められている」が答えになるかな
805の冒頭あたりで各ラウンドの始まりのタイミングは明記されてるよ
（まあこれもやや曖昧だったかもだから、もし混乱したなら二行目冒頭を
「最初のチャイムが鳴り終わってから4^4分間」ではなく
「最初のチャイムが鳴った10秒後から4^4分間」に変えて読んでほしい） >>828
メッセージ転送のタイミングはラウンドの回数だけに依存するんですよね？
そしてメッセージはヘッダから本文までの部分はラウンドMで送る4本のメッセージは全部同一なんですよね？
ではどのラウンドでもメッセージの開始部分では四つのボタン全押しになるんじゃないんですか？ >>829
フッタが全て異なるんだから幼女が同時にボタンを押すことはないでしょう
1ラウンド目なら、幼女0はラベル0をつけたボタンに"0330"を、ラベル1をつけたボタンに"0331"を…という感じで送るんだから
「メッセージの開始部分で４つ同時押し」てどういうこと？
上記の例で言えばメッセージ自体の開始部分は一文字目ということになるけど
この「メッセージの開始部分」は時間を指す概念ではないよね、何を指したい？ >>840
ああ、メッセージの最初は有無を言わずにあらかじめ決められている時刻でそこではシグナル送らないんですね
だから取り決めに従っている幼女なら同時オンすることはないですね
でも最初のメッセージはヘッダも本文もフッタも全メッセージ同じじゃないんですか？
最初のメッセージは全ボタン全押しじゃないんですか？ イヤ全幼女最初のメッセージは全ボタン全押しじゃないんですか？
全部違うタイミングだけど1人の幼女が押すタイミングは全部同じになりますよね？
この時点で悪魔は義務を果たせてしまいます 幼女が最後につける番号は0,1,2,3と違う番号をつける事を義務付けるんですか？
それはほんとに区別できるんですか？
例えば幼女3が4本の回線に0,1,2,3とつけて悪魔が回線番号に1,0,0,0とかつけて義務を果たしてきた場合それはどこかのタイミングで必ず発覚するんですか？ >>833
> 幼女が最後につける番号は0,1,2,3と違う番号をつける事を義務付けるんですか？
うーん…805に書いてあるこれ↓読んでもろて
> ラベルとは、事前に自分の手元にあるボタンに互いに異なるよう振った番号とし、ボタンと番号の対応はゲーム中不変とする。
厳密に書いたつもりなんだけどなあ…
きっと何度も聞かれるのはわかりにくいからなんだろうなあとは思うから、そこは申し訳ないんだけど…
> それはほんとに区別できるんですか？
> 例えば幼女3が4本の回線に0,1,2,3とつけて悪魔が回線番号に1,0,0,0とかつけて義務を果たしてきた場合それはどこかのタイミングで必ず発覚するんですか？
する。（勿論それを保証するために証明がある訳だから）
例示してもらったパターンは大きさ3のチームができるパターンかな？
>>818-819 で(1)と(2)に場合分けして示してある。 あ、チームは関係ないか、すまん
まあしかし証明見てもらえばわかる通り、フッタが活きるのは大きさ3のチームができた時だからね
もしすべての幼女が他の誰かから直接的に信頼されてる場合は、３つ目の補題から、フッタの情報を使わずに悪魔を特定できるから そうです
おそらく悪魔の最良の選択はもちろん3幼女と誰からも信頼してもらえない1幼女に分ける、すなわち全ての幼女に幼女3のふりをするとかの戦略で、問題は各回線に割り振る番号を
同じもの３つにした場合(既に義務を果たしている場合)
同じもの２つと違うものの場合(義務を果たしていない場合)
３つとも違う番号にした場合(義務を果たしていない場合)
の前者と後2者を区別して
前者なら誰がそれをやったのか、
後者ならそれを見極めていつか発覚できると断言できるか
です
例えば最初の私の誤答だと
幼女3の割り付けが1,2,3、悪魔の割り付けが0,0,0の場合は既に義務を果たしていていつまで待っても不正は発覚せず
幼女3の割り付けが0,1,2、悪魔の割り付けが3,0,0の場合は義務を果たしていていつか待ってれば不正は発覚するがもしかしたら前者のような不正をしてるかもしれないのでいつか発覚すると断言はできない
幼女0,1,2が受信している番号付けでは
前者は1-0,2-0,3-0
後者は0-3,1-0,2-0
で同じなので区別がつかずコレだけではどうしようもなくて失敗したんです
つまり少なくとも回線番号の割り当てられ方のセットだけでは少なくとも判定ができません
もちろん手がかりはそれだけではないので、特にプロトコルに色々取り決めがあるのでそれも手がかりにすればなんとかなるのかもしれないですがちよつ証明の行間ぎ広過ぎて読めてないんです うん、やっぱりわからない
上の例ではどのように悪魔は特定されるんですか？
証明ではB≠bですか？
ど頭から違うフッタつけてきた場合ですけど
この場合幼女0,1,2には>>836の例では
0031 0032 0033
0030 0030 0030
と送られてくるわけですよね？
もちろん幼女3を名乗る2人のどっちかが不正を行ってますけどそれどうやって確定するんですか？ やってみました
最初のターンで幼女3と悪魔が送ってくるメッセージは
3330 3330 3330
3331 3332 3333
これらを受けて次のターンで幼女iが次に送るメッセージは
i〜33033120
i〜33033221
i〜33033322
ただし〜は幼女012間の通信で第1ターンでは全く同一
これらを受けて第3ターンで幼女0,1,2が受け取るメッセージは
3〜33033120〜33033221〜33033322110
3〜33033120〜33033221〜33033322111
3〜33033120〜33033221〜33033322110
3〜33033120〜33033221〜33033322112
3〜33033120〜33033221〜33033322110
3〜33033120〜33033221〜33033322113
この時点までは悪魔を特定できないのではないでしょうか？
0が多いのは確かですけど第1ターンでもらったメッセージから判定出来なかったのと同じ理由で判定出来ないのではないですか？
次のターンから〜部も関わってくるのでわかんないのですけど 0が多いのでもうこの時点で第1ターンから悪魔が不正なフッタを使っているのはもちろん確定できるとして幼女0,1,2もどちらの回線が悪魔の回線か確定できてないですよね？ >>837
うん、そのパターンは819で最初に排除してる n=1 の場合に該当するね。
2ラウンド目で幼女0,1,2が幼女3と名乗る２人から送られるメッセージは
3b1 3b2 3b3
3B0 3B0 3B0
（ただしb,Bはそれぞれ幼女、悪魔が送った本文とする）
となる。
もしb=Bなら
3B1 3B2 3B3
3B0 3B0 3B0
となるから、ここから更に悪魔を特定するにはBの内容が必要という認識は合ってる。
もしかしたらここも隠れたミソなのかも知れないけど、もし２つの本文bとBが等しければ、勿論その内容は「本物の幼女3が発した本文bと等しい」訳だから、
その内容には、本物の幼女3が受け取った情報が含まれている。
そしてその情報には、1ラウンド目で誰を名乗る者から何が送られたかが含まれる。
（例えば「信頼できる幼女1から"1332"が送られた」とか。
この場合、そのメッセージを受け取った幼女1は「じゃあ1ラウンド目に自分が"1332"を付加して送信した方が本物の幼女3なんだな」と導ける）
…ということを示したのが819の投稿。 >>840
それで結局>>838ではどうやって000と123フッタの場合と
012と300フッタの場合を見分けるんでしょうか？
結局永遠に違いは末尾の0と1、0と2、0と3しか出ないんじゃないですか？
メッセージが長くなっても情報変わってないような まぁでも信用状態は2回目からは幼女0,1,2に対しては2、幼女3と悪魔からは1(悪魔は幼女3に対して3を名乗るとします)でコレも特に役に立たないですよね？ あ、イヤ違う
この場合にはとりあえずダメ元で幼女0,1,2は全部ラベル0につながってる方で試してみればいいですね
それで悪魔が死ねばよし
ダメなら012に300重ね、023に100重ね、013に200重ねのいずれかで悪魔はまだ義務果たしてない事が確定するからそこからは全幼女何にもしないでボケーっとしとけばいいですね
このチャレンジで幼女3が死ぬこともない >>841
000と123か、012と300のどちらのパターンだったのかは、いずれ発覚するかもだけど、その情報をもとに悪魔が特定される訳ではないからなあ…
特にこのケースでは、下記の通り、幼女0,1,2は「自分たちが受け取ったメッセージの集合」ではなく
「自分がどのボタンから何を送ったか」と「自分がどのボタンから何を受け取ったか」をもとに悪魔を特定することになるし。
（悪魔だって、幼女3であると騙ることはできても、実際に幼女3のボタンを押して幼女1のボタンを光らせることはできないから、それを利用した戦略とも言える）
838の3ラウンド目に幼女3（と悪魔）が送った本文を翻訳すると、内容を抜粋したら
「2ラウンド目に幼女0から送られたラベルは0、幼女1から送られたラベルは1、幼女2から送られたラベルは2でした。悪魔は特定済みです」
が含まれるはず。
（信用状態が全部1ってことはそういうケースを考えてるで合ってるよね？）
これを受け取った幼女1は、自分が2ラウンド目にラベル1を付加してメッセージを送信したボタンを思い出して
「ああ、このラベル1のボタンの先に本物の幼女3がいるのか」と判断する。 だから私の最初の解答でもできるんだ
まず最初に幼女は自分の名前と4本のボタンのどれで通信してるかの情報を受け手がわかる形で宣言する
宣言を受けて各幼女は同じ幼女を名乗る2回線と本物と確定できる2回線に分けられる
同じ回線を使って各幼女は自分がまだ信頼できていない1回線(未承認幼女と呼ぶとしましょう)を信頼できる回線２つにポストする
この時点で信頼のチームが4一個なのか3+1に別れてるのかが少なくとも3人にはわかる
何故なら後者の場合、チームが{0,1,2}+{3}に分かれていた場合全員信頼している回線から未承認幼女は2と報告され、前者では幼女0,1,2,3の未承認幼女がの3,3,0,2のタイプの時だけそれぞれの信頼してる回線からの未承認幼女の宣言が(3,0), (3,0),(3,2),(3,3)となるが他のケースでは全て2人の信頼してるチャネルからの未承認幼女は相異なる番号が宣言される、すなわち誤解は1ケースのたった1人にしか起こらない、そしてその場合にも誰かが「大丈夫、4人チームだった」と宣言して悪魔処刑を開始できる
3人チームの場合、悪魔は3人に対してある幼女を装って振る舞っている事になるけどこの時仮に偽幼女3をなのっているとして幼女0,1,2は幼女3と偽幼女の回線番号宣言を調べる
この時点で悪魔が義務を果たしているならいずれかの回線番号が3回使われている
そこでその3回使われてる番号の主が偽物と仮定してとりあえず処刑できないか試して見る
成功ならそれでよし、ダメならこれ以上追求の手段はないが悪魔もこの時点では義務を果たせていない事が確定する
なのでもう黙っておく、3番幼女も信頼できる幼女から処刑開始宣言が出されるまで黙る
初期情報との違いはこの時点では3人の相互に通信できる幼女チームと残りの1人は3人にメッセージは送れないがメッセージは受け取れる状態は確立できている事
そして悪魔はまだ義務を果たしてないのでいずれ3人チームの誰かのボタンを光らせるしかない、そのときそのチームのメンバーが処刑の開始を宣言すれば良い 結局この問題この「ダメ元でやってみる作戦」が禁止されてないのでこういう解もあるんだな
もしコレが「トライは一回のみ、それでダメなら悪魔の勝ち」ルールならこの“各幼女は四つの回線に好きに番号つけて大丈夫”というわけには多分いかないんだと思う、証明はできないけど、多分その場合には「まず悪魔の出方をみてそれに応じて回線番号をうまく割り振らないとダメ」といういわば“後手必勝”のゲームになるんだと思う
中々面白かった >>846
> そこでその3回使われてる番号の主が偽物と仮定してとりあえず処刑できないか試して見る
> 成功ならそれでよし、ダメならこれ以上追求の手段はないが悪魔もこの時点では義務を果たせていない事が確定する
ん？これは本当に確定する？
悪魔が幼女1,2,3に対して自分が幼女3であると騙った場合も？ >>848
正確には、幼女1,2,3に全く同じメッセージを送ることで義務を果たした場合も？ >>848
例えば悪魔が偽幼女3を名乗ってなおかつ義務を果たしている場合、すなわち同一回線を3個使っている場合、幼女3が幼女0,1,2に開いている回線が0,1,2として一般性を失わず、悪魔が使っている回線は0,0,0か3,3,3として一般性を失わない
前者なら幼女0,1,2に開かれる回線は0と0,0と1,0と2となるのでこの情報を3幼女は交換して幼女0は悪魔の回線を特定できないが残りの2幼女は悪魔の回線を特定できる
問題は悪魔が3,3,3を使用してきた場合
この場合幼女0,1,2に開かれる回線は3と0,3と1,3と2になってしまう、これは幼女3と悪魔の回線が
幼女3 3 1 2 , 0 3 2 , 0 1 3
悪魔 0 3 3 , 3 1 3 , 3 3 2
の場合と被りこの場合は誰も悪魔への回線を特定はできない
しかしいずれのケースも悪魔はこの時点では義務を果たせていない
だからまず幼女は全幼女3番回線使ってるボタンを全押し、幼女3は全ボタン押しすると計6個のボタンが通電する部屋は全てのケースで
幼女0部屋×1 + 幼女1部屋×1 + 幼女2部屋×1 + 幼女3部屋×2 + 悪魔×2
となって仮に悪魔が全押ししても幼女も悪魔も誰も死なない、死なないけど残念でしたにしか過ぎずルール上幼女はまだ負けていない、実際この時点で全幼女悪魔のボタンは2択までは確実に絞れていて、しかも幼女3以外の3人のもう一つのボタンは幼女3と確定している
だからここから幼女3は2人以上から起こされない限り眠りにつく、他の幼女はどれかのボタンが点灯するまで眠りにつくを実行する
悪魔は幼女3以外のどれかのボタンを押さないと誰も起きない、しかし幼女3以外のどれかのボタンを押せばその瞬間悪魔の敗北が決定する、そして義務を果たせていない悪魔はどこかの時点で幼女3以外のどれかのボタンを押さざるを得ない >>850
> 問題は悪魔が3,3,3を使用してきた場合
> この場合幼女0,1,2に開かれる回線は3と0,3と1,3と2になってしまう、これは幼女3と悪魔の回線が
> 幼女3 3 1 2 , 0 3 2 , 0 1 3
> 悪魔 0 3 3 , 3 1 3 , 3 3 2
> の場合と被りこの場合は誰も悪魔への回線を特定はできない
> しかしいずれのケースも悪魔はこの時点では義務を果たせていない
うん、やっぱり果たせるはず。
なぜなら、例えば
幼女3 3 1 2
悪魔 0 3 3
のパターンで、悪魔が幼女3に対しても回線3を開けばいい。 >>851
あ、ホントだ
やっぱりダメだね
やっぱり回線番号自由に使えるならダメだ
やっぱりこのゲームは“後手勝ち”で悪魔の出方見て回線番号割り振らないとダメなんじゃないかな
その方法とかはどうでもいい気がする 845でも書いたけど、幼女0,1,2は幼女3と悪魔からの情報が、それぞれどっちのボタンから来たのかも判断材料に含めることができる、ということを念頭に置いた上で、証明を追ってもらえたらわかると思う
神視点で838に足りない情報は、3ラウンド目に受信した各情報が、2ラウンド目に何を送ったボタンから送り返されたものなのか、だよ >>853
え？どういうことですか？
>>838は3ラウンド目に受け取った情報ですよね？
コレ見てどうやったら
0 0 0
1 2 3
と
0 0 3
1 2 0
の区別がつくんですか？
〜部は全く同じ列が並んでいて違いは末尾の数字だけで一ラウンド目と何も変わってませんよね？
ここでわかるなら1ラウンド目でわかってるんじゃないですか？ ともかく私の読解力では証明は何言ってるかさっぱりわかりません
まずそもそもある時点で悪魔が同一のメッセージを送った場合に本当に何ラウンド目かに誰か1人がそれを見つけることができるかですよね？
どこでどう示されてるんですか？
1ラウンド目で悪魔と幼女3が0 1 2 3に
3330 3330 3330 3330
3331 3332 3333
から始めた場合と
1ラウンド目で悪魔と幼女3が
3330 3330 3333 3330
3331 3332 3330
から始めた場合とで何か差が出るんですか？ 何言ってんだオレorz
幼女3 3 1 2 , 0 3 2 , 0 1 3 , 0 1 2
悪魔 0 3 3 , 3 1 3 , 3 3 2 , 3 3 3
しか可能性ないんだから幼女は
0 3 3, 3 1 3, 3 3 2, 3 3 3
全部やってみりゃいいだけやん
どれも幼女3死なないんだから 838に「3ラウンド目に受信した各情報が、2ラウンド目に何を送ったボタンから送り返されたものなのか」の情報が足りないと言っている
だから付け足して考えれば良い。第3ラウンドで各幼女が受け取ったメッセージが
幼女0：
3B10←前のラウンドで0(中略)20を送ったボタン
3B11←前のラウンドで0(中略)23を送ったボタン
幼女1：
3B10←前のラウンドで1(中略)21を送ったボタン
3B12←前のラウンドで1(中略)23を送ったボタン
幼女2：
3B10←前のラウンドで2(中略)22を送ったボタン
3B13←前のラウンドで2(中略)23を送ったボタン
だった場合と
幼女0：
3B10←前のラウンドで0(中略)23を送ったボタン
3B11←前のラウンドで0(中略)20を送ったボタン
幼女1：
3B10←前のラウンドで1(中略)21を送ったボタン
3B12←前のラウンドで1(中略)23を送ったボタン
幼女2：
3B10←前のラウンドで2(中略)22を送ったボタン
3B13←前のラウンドで2(中略)23を送ったボタン
だった場合で何が変わるか考えればいい。
もしBに「2ラウンド目に信頼できる幼女0から0(中略)20が送られてきました」という内容が含まれていれば、
幼女0は、上のパターンなら3B10を送ってきた方、下のパターンなら3B11を送ってきた方が本物の幼女3とわかる。
もしBに「2ラウンド目に信頼できる幼女0から0(中略)23が送られてきました」という内容が含まれていれば、
幼女0は、上のパターンなら3B11を送ってきた方、下のパターンなら3B10を送ってきた方が本物の幼女3とわかる。
どちらのパターンでもやってることは同じなのよね 「自分が何を送ったボタンから送り返された情報なのか」も各幼女は情報として使うことができると言ってるのに
その情報を遮断し続けて、大きさ3のチームに属するすべての幼女が得られる情報でしか判断しようとせず「どうやって区別するの」は、
そろそろ解決してほしいなあ 欧米で１年間の性交回数が平均１００回で
避妊しない場合の妊娠の確率が８５％だったそうです
１回で妊娠できる確率は相当低いのだろうなと思うのですが
計算の仕方がわかりません
教えてください
ちなみに単純に
0.85 = X ^100
とやったら
ln0,85=100*lnX, lnX=ln0.85/100, X=exp(ln0.85/100)=0.998
100%近くなってしまいました >>857
イヤ、まずそもそも悪魔はプロトコルを守るなんて限った話ではない、好きなこと書いていいんだから
悪魔がやらないといけないのは少なくとも毎回フッタの情報は同じものが強制されるということ
これはプロトコル上通信相手の幼女から前回の通信記録と照らし合わされると直ちに不正が判定されてしまうから
本文については前回のものと違うものを書いてもいいんだからここにはまだ偽造の余地があるし本当に悪魔が手を加えてきても必ず判定されてしまうかどうかなんかわからんやん？ 実際>>838の〜のところに悪魔が手を加えてきて01,02,03型の時の場合と01,02,30型の時を偽造してきた場合どうやってそれを見抜くの？ >>769>>770
こういう問題は、文章のみの説明では分かりにくく誤解などもしやすいので、絵図などを使用して欲しいですね つまり>>818のココ
ここで、同一の本文を送らなければならないというプロトコル上の制約から、Bを送った人とbを送った人を区別することができるが、
コレは悪魔がプロトコルを守ってるという前提の元で議論してる
しかしもちろん悪魔はプロトコルを守る義理はない
悪魔に課せられているのは「プロトコルを守っていると仮定すると矛盾してしまうほどの改変はしてはいけない」というだけ
この範囲ではいかなる改変も不可能というのは自明であるとはとても良い言えんやん？ もちろん
> 悪魔に課せられているのは「プロトコルを守っていると仮定すると矛盾してしまうほどの改変はしてはいけない」
というのはあくまで悪魔の方の返信はプロトコルを守っているが幼女3'の３つの返信は好き勝手に改変されていると仮定した場合に矛盾が生じるかという話
つまり(X₁〜Xₙ,Y₁〜Yₙ)と(X'₁〜X'ₙ,Y₁〜Yₙ)を長さが
1+2+1 , ((1+2)×3)+2+1, (((1+2)×3)+2+1)×3+2+1,...
の0,1,2,3からなる文字列であるとする
コレをそれぞれ悪魔からの返信と幼女からの返信と見做してみるとする
この時
(Xₖ)はプロトコルを守った返信で(Yₖ)はそうでないとし、
(X'ₖ)はプロトコルを守った返信で(Yₖ)はそうでないとする
(そのような場合幼女0,1,2間の通信は(Xₖ)から確定するからキチンと数学的命題として意味を持つ)
とのとき必ず(Xₖ) = (X'ₖ)であると言えるか？
フッタが等しいはもちろん言える
本文まで正しいと言えるのかが問題
とても自明ではないやろ まだ不正確やな
(Xₖ)はプロトコルを守った返信で(Yₖ)はそうでないとし、
(X'ₖ)はプロトコルを守った返信で(Yₖ)はそうでないとする
これは
(Xₖ)はプロトコルを守った返信で(Yₖ)はその限りではない、守ってるかもしれないし守ってないかもしれないしないし(つまりこっちが悪魔で好き勝手な事書いてるかもしれないとし)
(X'ₖ)はプロトコルを守った返信で(Yₖ)はその限りではない、守ってるかもしれないし守ってないかもしれないしないし(つまりこっちが悪魔で好き勝手な事書いてるかもしれないとし)
た場合(Xₖ) = (X'ₖ)と言えるのか
もちろん悪魔が全く偽造をしていないプロトコル通りの返信があってそれはプロトコル通りの返信をした場合と矛盾しない、この文字列と同じというのが「プロトコル通りの返信として矛盾しない」の数学的意味合いだから当たり前、問題は「その様な文字列は本当に一つしかないのか？ホントに悪魔にプロトコルに矛盾しない文字列はひとつしかあり得ないのか？」
コレが正しくない限り「プロトコル上どうのこうの」という議論はできない、悪魔がプロトコルを守るなんてわからないから >>860
「本文は毎ラウンド違うし騙られ得るからそこからは何も情報を得られない」と思ってるなら、下記を読んで考えを改めてほしい（読まなくても気づいてほしいが）
そもそも「同一ラウンドで同一の幼女から送られる本文（全文じゃないぞ、ヘッダとフッタは含まれない）は全て一致しなければならない」というプロトコル上の制約を悪魔が破ったら、
大きさ3のチームお得意の情報共有で即座にそれを見抜かれるということを認識してもらいたい
大きさ3のチームに対して幼女3と名乗る者からnラウンド目に送られた本文が例えば
b1, b1, b1, b2, b2, b3 (b1,b2,b3,…は互いに異なるとする。以下同じ)
だったら、b2, b2, b3を送った者が悪魔であることが（n+1ラウンド目に大きさ3のチーム内でなされる情報共有でチーム内の全員が）わかる。
なぜなら、b2を送った者は同じ内容を大きさ3のチーム全員に送っていないことがわかるから。b3を送った者についても同じ理屈で悪魔確定。
これが b1,b1,b1,b1,b2,b2 だったとしてもb2が悪魔だし、b1,b1,b1,b2,b3,b4 だったとしても b2,b3,b4 が悪魔。
結局のところ、得られた本文が b1,b1,b1,b1,b1,b1 か b1,b1,b1,b2,b2,b2 でなければ上記の理屈で全て見抜かれる。
つまり悪魔も、少なくとも大きさ3のチームに対しては、全く同じ本文を送る以外に手立てはないということ。
じゃあ悪魔が全く同じ本文を送ってたら？というケースについて論じたのが >>818 の(1)と >>819 の(2)の議論。 あったあった、>>794 で書かれてるのと同じ理屈なのよこれつまり。
> この6個のチャネル開始フェーズを調べる
> 幼女3からのチャネルは必ず同一フェーズで開始されていなければならない、よってある種別3のチャネルで同一フェーズで開始してる種別3のチャネルの数が3未満のものが有ればそれは悪魔からのチャネルであると特定できる
「本物からは全く同じ情報が送られる」ことがせっかく保証されてるんだからうまく使えないはず無いのよ >>856
なんかあんた口悪いよ
いつもあんたと喋ってるとそうだよ
あんたそもそも相手見下してるやろ心の中で？
ちょっとこっちにもそろそろ限界まで来るよ？
もうちょっと考えてほしい まぁムカつくけど家帰ったらよんでみるよ
ただいつもあんたのレス読むけどあんたそこまで上からしゃべれるほど頭良くないよ あー…とは言え確かに >>866 の内容を書かなかったのはさすがに証明すっ飛ばし過ぎたか
そこがネックでずっと理解できずにいたなら申し訳ない >>870
わかっていただけだなら結構です
少しムカッときてしまって止められませんでした まずとりあえず悪魔の改変とは「本体が3幼女に異なる内容を送る」という意味ではない
証明しないといけないのは
「入力された情報から得られる本文とは違う内容の本文を使った
場合」
でプロトコルが「本文が同じ内容でなければならない、同じ内容なら何でも良い」
なら
「プロトコルに違反した文字列で矛盾する」
の背理法の仮定はそれでいいけどそんないい加減なプロトコルではないでしょ？
プロトコルは「与えられた四つの入力のヘッダーを取り除いてつなげたものを本文とする」
なんだから背理法の仮定て仮定できるのは「与えられた四つの入力のヘッダーを取り除いてつなげたものでないものを本文とする」
である事 つまり流石に悪魔はヘッダには“３”をつけるしフッタは3幼女iに対しては“1”+iをつけるかもしれないけど本文については3幼女に同じものを送る限りにおいては入力された4っの文字列からヘッダーを取り除いてつなげたもの以外のものを採用した場合、3幼女はその３つを突き合わせて比較しても「一致はしてるね」までしか言えない
つまり３つが一致してるかどうかの判定だけでは悪魔が全く手を加える余地がないとは言えない
つまりこの検査をパスする改変された返信は可能なので改竄の余地はなくプロトコルを破れる余地はないとは言えない
なので悪魔がプロトコルを守るなどということはこの付き合わせで本文の一致を確認する検査だけでは不十分です 前>>718
>>859
85%÷(100回/1回)=0.85%
∴0.85% >>872
大きさ3のチームの各幼女が、幼女3か悪魔かわからないボタンから送られた本文の内容を実際に参照する必要が生じるのは
>>819 の(2)のケースになった時だけだから、そこも問題無いと考えてるけどどうだろう。
悪魔がプロトコルに従わない本文Bを送信して、それがたまたま幼女3の本文bと一致すれば（(2)のケース）その本文b=Bの内容を信用してしまえば良いし、
Bが幼女3の本文bと一致しない時は、本文Bに付随するフッタのうち一致するものがあれば（(1)のケース）それをもとに悪魔が特定される。
本文bとBが一致せず、Bに付随するフッタもバラバラなら、それは悪魔がまだ義務を果たしていないだけということがわかる。 なんか言葉足らないな
言いたいのは
「プロトコル上〜」という議論ができるのは悪魔が絶対プロトコルを破る通信をした場合必ず見破れるという事の保証がないとできない
では悪魔がプロトコルを守らなかったら、すなわち本物の幼女3ならこう返すはずという以外の返信をしたらが背理法の仮定
ではそれは幼女3以外の名前を名乗ってさたらとか前回と違うフッタを使ったらなんてのは問題外として本文部分の改竄、すなわち「入力された4入力からヘッダを取り除いてつなげたもの」以外のものを使った場合というのが背理法の仮定
そこの一部を改竄してあとは全部プロトコルに従う場合、3幼女には同じ改竄文書が届く、しかし付き合わせて比較するだけでは改竄があった事は発覚しない、すなわち
「改竄があった場合、付き合わせ検査で必ず発覚するので本文まで考えればあらゆる改竄は不可能、よって悪魔はプロトコルを遵守しない限り見破られてしまう」という主張はおかしい
悪魔がそのような改竄をした場合でも“付き合わせ検査”以外の検査も併せて行えば必ず改竄が発覚する事を証明しなければならない
今見た通り付き合わせ検査だけでは「3幼女に違う本文を送る」というスーパー間抜けな改竄をした場合しか3幼女は改竄を見抜けません >>875
わからないけどとりあえず付き合わせ検査ではすり抜ける改竄があるのだから「ありとあらゆる改竄が不可能」という主著のもとに議論するなら証明してください >>877
証明の中で「悪魔がプロトコルに従う」という仮定は「していない」というのが答えかな
証明中で「プロトコル上」と言ったら、それは「幼女はプロトコルに従う」という事実を使ったつもり。
例えば >>818 では
> （プロトコルからpがq,rに対して送る本文は同一）
というのは幼女pがプロトコルに従うことから導いているし、
> ここで、同一の本文を送らなければならないというプロトコル上の制約から、Bを送った人とbを送った人を区別することができるが、
という一節は
「幼女3はプロトコルに従っているので同一の本文を送るはず。
なので大きさ3のチームに属する幼女は、本物の幼女3が自分たちに送った本文がb,b,bかB,B,Bのどちらかであることを導くことができる。
どちらの場合も、悪魔が送った本文も全て一致することになる。」
ことを言っているし、
> Bを送った人が同じフッタを別々の幼女q,rに送ったことがわかるので、プロトコル違反によりq,rは悪魔を特定できる。
という一節は、
「大きさ3のチームに本文Bを送った同一人物は、プロトコル違反をしたから幼女3ではないと導ける。」
ということ めんどくさいのて幼女0,1,2はメッセージ受け取った時点でメッセージの照らし合わせ照合できるとします
悪魔がど頭からフッタを改竄した場合、幼女が悪魔への回線を特定できるのは何ターン目のメッセージを受けた時ですか？
2ターン目にそれぞれが長さ15のメッセージもらったとき
この15文字×3のメッセージの照らし合わせで発覚するんですか？
それとも次の3ターン目の長さ59のメッセージ3個の時点ですか？
具体的にノートに本文全部書き出してみると2ターン目までで矛盾はもちろん発覚してるけど悪魔の確定まではできないみたいだけどコレ次の3ターン目のメッセージ照らし合わせで000型不正と300型不正の違いを断定できるんですか？
もう昼休み終わるので続きは寝る前ですな すいませんがもう仕事戻りますが具体的に
・幼女iは幼女jにラベルjの回線を割り当て、悪魔には回線iを割り当てている、よって1ターン目では幼女jにはi33jを、悪魔にはi33iを送る
・悪魔は1ターン目で幼女に全部3333を送るという不正メッセージを送る
の場合、以下悪魔がどんなにうまく立ち回ったとしても不正回線を見抜かれるのは何ターン目ですか？ 何ターン目ですかというのは何ターンめのメッセージ受け取った時ですかの意味です
nターン目のメッセージは長さ(11×4ⁿ+4)/12のメッセージを受け取る時
1ターン目 (44+4)/12 = 4
2ターン目 (176+4)/12 = 15
3ターン目 (704+4)/12 = 59
この辺で確定しますか？ >>880
まず桁数について誤解を解きたい。
nラウンド目に送られるメッセージはちょうど4^n桁になることに注意。
メッセージ全体からヘッダ1桁とフッタ2桁を除いた残りの本文は、
4^(n-1)-1 桁の塊３つと 4^(n-1) 桁の塊１つで構成される。
（プロトコルの本文についての記載参照）
その上で、幼女たちは【どんなに遅くとも2ラウンド目終了時に悪魔を特定できる】というのが質問の答えだね
勿論、指定してもらったように、幼女0,1,2間の照合も込みでの答えになるけど
（もし照合を外せば最遅で3ラウンド目になる）
【1ラウンド目】
幼女0：
ラベル3のボタンから3330が送られる
ラベル0のボタンから3333が送られる
幼女1：
ラベル3のボタンから3331が送られる
ラベル1のボタンから3333が送られる
幼女2：
ラベル3のボタンから3332が送られる
ラベル2のボタンから3333が送られる
※このうち「ラベル○○のボタンから」にあたる情報は、次のラウンド以降のやり取りでも明示的には共有されないことに注意。
なので、幼女0,1,2間の照合もその前提に従うものとする。2ラウンド目以降も同じ
【2ラウンド目 パターン1】
※幼女3および幼女3を騙る悪魔から送られた信号は、わかりやすくするため、下記の凡例のようにスラッシュ『/』で区切ることとする。
※凡例：
ヘッダ/幼女0からの本文とフッタ/幼女1からの本文とフッタ/幼女2からの本文とフッタ/悪魔からの全文、あるいは300…/フッタ
幼女0：
ラベル3のボタンから3/333/333/333/3000/10が送られる
ラベル0のボタンから3/330/331/332/3000/13が送られる
幼女1：
ラベル3のボタンから3/333/333/333/3000/11が送られる
ラベル1のボタンから3/330/331/332/3000/13が送られる
幼女2：
ラベル3のボタンから3/333/333/333/3000/12が送られる
ラベル2のボタンから3/330/331/332/3000/13が送られる
→ラウンド終了時に幼女i (i=0,1,2)は以下に気づく：
本文 330/331/332/3000 を送った同一人物が全て同じフッタになっている。したがって私がラベルiを付加した方のボタンが悪魔だ。 【2ラウンド目 パターン2】
幼女0：
ラベル3のボタンから3/333/333/333/3000/10が送られる
ラベル0のボタンから3/333/333/333/3000/13が送られる
幼女1：
ラベル3のボタンから3/333/333/333/3000/11が送られる
ラベル1のボタンから3/333/333/333/3000/13が送られる
幼女2：
ラベル3のボタンから3/333/333/333/3000/12が送られる
ラベル2のボタンから3/333/333/333/3000/13が送られる
→ラウンド終了時に各幼女i (i=0,1,2)は以下に気づく：
どちらのボタンが本物の幼女かはわからないが、333/333/333/3000 が本物の幼女3から送られた本文そのものであるのは確かだ。
これを解読すると「1ラウンド目で幼女iから"i333"が送られました」だから…
つまり、私がラベル3を付加した方のボタンが本物の幼女3だ。 >>882
そのケースにおいて悪魔がどんなに返信の内容を改竄してもターン２で自分の正体が発覚しないのは何故ですか？
それは「悪魔が幼女３の振りをして返信プロトコルに従わない一切の改竄をしなければターン２で自分を特定されてしまう」一例に過ぎないですよね？
悪魔が自分の正体がターン２では存在しない理由はなんですか？ (幼女たちがどういう場合にどのように動くのかだけ書いてくれたらそれで大丈夫か考えてみるんだけど、長々と2人で議論してるところにそれ言うのも気が引けるなぁ…) >>886
なんの事ですか？
私出題者じゃないけどわかる範囲なら答えますよ やっぱり変なんじゃないですか？
結局>>883の推定ってこの話ですよね？
nラウンド目に悪魔とpからq,rに対して送られた本文 b(=B) には、n-1 ラウンド目にpがq,rそれぞれから受け取ったフッタの情報が含まれる。
したがってq,rはどちらも、自分がn-1ラウンド目にどのボタンからどのフッタを送ったかの情報と照合することで、
どのボタンが本当のpに通じるボタンかを特定することができるので、もう片方が悪魔であるとわかる。
つまり>>819のこの話
コレのn=2の場合をアプライしてるようですけどコレで“n-1ターン目のpの本文”を使う事が前提でそれが使える理由が「B=bだからどっちが悪魔だとしてもn-1ターン目のpの情報が使える」って話だと思いますけど、それは悪魔がnターン目に本文の改竄をしないという前提で話してませんか？
それをされると「n-1ターン目のpの情報使う」がそもそも不可能になりますよ？
でも前の方で「悪魔が本文改竄しないという仮定は話に入ってない、だから証明もしてない」って言ってだと思います
だからやっぱりその証明要りますよ >>886
各幼女がどう行動するかはほとんどプロトコルでガッチガチに決められてるからなあ
行動の変化の余地があるとすれば
・最初の各ボタンへのラベル付け（これは自由というより無作為と言った方が良い）
・悪魔判定とそれに伴う信用状態の発信（これも各幼女の完全な論理性を仮定すれば自由度は無いはず）
・2ラウンド目以降で悪魔かどうかを特定できていないボタン２つのうち、どちらから来たメッセージを、次のラウンドで送る本文中の最後の4^(n-1)桁に埋め込むか（これは情報の内容を本質的に変えるものではない）
ぐらいだし、その中でいずれ悪魔が退治されることを示すのに専念すればいいと思うんだけど
とは言え「今各幼女に"完全な"論理性は仮定してないじゃん、
本当に完全な論理性を有する幼女が今議論してるよりももっと早いタイミングで悪魔を特定して、その後のラウンドで送信される情報が変わる可能性はあるけど、その場合もうまくいく保証はあるの？」
という反論は確かに考えられる。
ただこれも問題無くて、完全な論理性を持った幼女の推論は、究極的には
・自分含む各幼女が各ラベルをつけたボタンの先に誰がいるか
・上記の場合分けをして更にそのうち、まだ悪魔を特定していない幼女から受け取った本文の最後の4^(n-1)桁はどちらのラベルからのメッセージを載せたものか
に関する場合分けをして矛盾が生じない場合全てを洗い出すという作業と何ら変わりが無いものだから、
（※この「矛盾を導く」にあたって、悪魔がどう行動するかに関する如何なる仮定も置いていないことに注意。）
結局、本文最後の4^(n-1)桁の部分がヘッダ以外0で埋められた（つまり「こいつは悪魔でした」マスクで覆われた）メッセージは、そうでないメッセージよりも真に強い情報を持っていると言える。
（場合分けの一部を削ったものと言える訳だからね） >>885
このケースでなぜ2ラウンド目終了時に悪魔が特定「されない」のかを聞いてるで合ってる？幼女0,1,2間の照合無しでってことよね？
照合無しでは、例えば幼女0が全員から受け取る情報は
ラベル1のボタン（幼女1）から：1/331/331/331/3333/10
ラベル2のボタン（幼女2）から：2/332/332/332/3333/10
ラベル3のボタン（幼女3）から：3/333/333/333/3000/10
ラベル0のボタン（悪魔）から： 3/330/331/332/3000/10
であって、これでは幼女0視点でラベル0の先に幼女3が、ラベル3の先に悪魔がいる可能性を排除できないから、という理由になる >>888
> 悪魔がnターン目に本文の改竄をしないという前提で話してませんか？
してない。使ったのは「本物の幼女3が改竄をしていない」という事実だけ。
nラウンド目に悪魔から送られ（て、たまたま同じラウンドに幼女3から送られた本文と一致し）た本文は、
「悪魔から送られたものである」以前に「幼女3から送られたものでもある」訳だから、
「私は幼女3です。幼女0を直接的に信頼しています。幼女0からn-1ラウンド目に受け取ったラベルはLです」
という情報を「本物の幼女3が送った」ことに変わりはない。 >>890
イヤ、ちがうんですけどもういいです
先手でも幼女の勝ち”、つまり“悪魔の第一手目”を待つことなく幼女が”十分強い信頼の強い通信のネットワーク”を有限時間内(2時間程度)に構築してその間に悪魔が義務を果たしていれば処刑、そうでなくても義務を実行したら2分後に処刑」の解見つけました
多分あってると思いますけど精査してから上げます いかに幼女の必勝戦略を示す
この戦略は
準備プロセス(16+12+6分)
審判プロセス(4+2+2分)
待機プロセス(悪魔が義務を実行するまで+2分)
処刑プロセス(1分)
で勝利できる戦略である
審判プロセスと待機プロセスは省略されうる
以下幼女4人と悪魔を合わせて参加者と呼ぶ
4人の幼女には0〜3の番号をあてがい幼女0〜幼女3と呼ぶ
ボタンの点灯でシグナルを送る事で各参加者は繋がる部屋に信号を送れる
点灯させることが許されているタイミングで点灯させることにより信号１を送り、許されているタイミングで点灯させない事で信号０を送るとする
幼女がある制限時間内に非負整数値を送信するときは送出期間中その整数の二進展開の各桁をビッグエンディアン(最低位から)で送信する
t+1回目のチャイムと共に点灯するシグナルを時刻tのシグナルと呼ぶ
幼女の各部屋の左のボタンから順に0,1,2,3番回線と呼ぶ
各プロセスにおいて幼女は使うチャネルのルールを変更するが処刑プロセス以外のどのプロセスのルールでもいずれの時刻においてもいずれかの幼女の送信が禁止されているので悪魔を含めて誰も処刑される事はない ・準備プロセス
準備プロセスにおいては以下のルールで通信を行う
ー準備プロセスチャネルルールー
(1)回線aのボタンはシグナルの時刻tがt≡a (mod 4)であるシグナルしか送ることができない
(2)１６分を1周期として下図□部分のところで各回線はシグナルを送出できない
幼女１：□１２３０１２□０１□３０□２３
幼女２：０□２３□１２３０１２□０１□３
幼女３：０１□３０□２３□１２３０１２□
幼女４：０１２□０１□３０□２３□１２３
まず各幼女は最初の16分間に111₍₂₎を送信して通信を開始する
この信号を解析すれば受信者はそのチャネルの送信者と割り当てられた回線番号を知ることができる
この時点で幼女は相手が幼女であると確定できる回線を２つ見出す事ができる
３つの回線でそれが可能である場合もあるがその場合にも任意の2回線を選びその相手の番号を承認番号として定め、残る番号を未承認番号と定める
各幼女は次の12分間で全回線に未承認番号を送信する
自分が承認した回線が送出した２つの未承認番号が一致しない事を確認した幼女は続く6分間で処刑プロセスへの即時移行賛成に投票するため全チャネルに1をポストしそうでなければ0をポストする
この時賛成票数が3以上であれば直ちに処刑プロセスへ移行し、そうでなければ審判プロセスに移行し準備プロセスを終了する ・審判プロセス
審判プロセスでは準備プロセスで承認している２つの回線からいずれも自分の番号を未承認番号としてポストされた幼女がただ1人発生する、この幼女と悪魔を合わせて被疑者と呼び、残りの3幼女を保安官と呼ぶ
保安官に幼女の番号の小さい順に番号を振り直し保安官0,保安官1,保安官2などと表するとする
審判プロセスでは以下のチャネルルールで通信を行う
ー審判プロセスチャネルルールー
審判プロセスでは最初の4分間は保安官のみ送信し次の2分間は被疑者のみ送信を行い最後の2分間は保安官のみ送信を行う
説明を簡略化するため幼女3が被告の場合について説明をするが他の場合はこれに準ずるとする
まず保安官は相手が幼女3用の回線で送信しているチャネルを１つか２つずつ持つ
まず保安官1,2は最初の4分でその相手が送信に利用している２つの番号を昇順に2回に分けて保安官0と2人の被告に送信する、１つしかなければ同じ番号を2回送信する
次の1分で各被告は保安官1の1回目の送信で送られた番号が自分のそれと同じである場合には0を、異なる場合には1を保安官0に向けてポストする、同様の事を次の1分で各被告は保安官2の1回目の送信で送られた番号に対して行う
最後の2分間は2人の被告の証言を2人の保安官1,2に保安官0は転送する
この時点で2人の証言に偽証があるとすれば保安官1,2に向けられている回線番号が異なるにも関わらず悪魔が偽証した事によりいずれかの回線がいずれの被疑者も使用していない事になってしまう場合である
この場合はその回線の相手が悪魔と確定する
そのような事態が発生しないのであれば2人の被疑者は正しい証言をしている事になる
よってこの場合には保安官0は2人の被疑者が3人の保安官に向けてどの回線番号を利用しているかを確定できる
以上によりこの時点でどの保安官も悪魔の回線を確定できないのであれば悪魔はいずれかの保安官2人に対して同一の回線番号を使用するという不正を行っていない事が確定する ・待機プロセス
審判プロセスで保安官、被疑者となった幼女はその役割をそのまま引き継ぐとする
待機プロセスでのチャネルルールは以下の通りである
ー待機プロセスチャネルルールー
保安官でない幼女は一切のシグナルの発効を禁止する
保安官はプロセス終了の宣言を示す他の保安官へのシグナルとプロセス終了を被告に通達するシグナル以外の発信を禁止する
待機プロセスにおいては被告である幼女は一切の行動をせず待機する
保安官は待機プロセスの開始までの時点でに悪魔の不正チャネルを確定した場合、もしくはいずれかの被告の回線からのシグナルを保安官が認めるまで待機を続ける
待機解除の条件を確認した保安官は次の1分に全保安官に不正発見の報告シグナルを発信する
続けて保安官0は被告であった幼女に待機プロセス終了のシグナルを送信し待機プロセスを終了する
・処刑プロセス
処刑プロセスにおいて悪魔への回線を確定しているボタンが確定している幼女はそのボタンを押下する
そうでないものは自分の未承認の回線のボタンを２つとも押下する >>894
幼女1,3,4の1番回線が幼女2に通じていた場合、悪魔が時刻1のシグナルを幼女2に送信したら、幼女2が全員からのボタン押下を受けて死んでしまうのでは？ >>897
あ、ほんとだ
もっと禁止増やさないとダメやな 0<α<β
連続関数f(x)が任意の実数xで
f(α-x)=f(α+x), f(β-x)=f(β+x),f(α)<f(β)を満たすとき
f(α)<f(γ)<f(β),f(γ)=f(x)を満たすxが0<x<βでつねに2n(f(γ))個(n(f(γ))∈ℕ)存在するならばβ=(k+1)α (∃k∈ℕ)であることを示せ ■ このスレッドは過去ログ倉庫に格納されています
