面白い数学の問題おしえて～な 41問目
レス数が950を超えています。1000を超えると書き込みができなくなります。
面白い数学の問題を紹介して解き合うスレです
質問スレではありません
出題者が答えを知らない問題はお控えください
統計学などはスレ違い、数学以外の話題は論外です
荒らし、煽りはスルー推奨
前スレ
面白い数学の問題おしえて～な 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/ >>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∈ℕ)であることを示せ >>899
何か条件が足りないかミスってる
例えば 2α<β<3α として、f(x) = α-x (0≦x≦α), x-α (α≦x≦2α), 3α-x (2α≦x≦β) とか f(β)=max(0<x<β)(f(x))
抜けてた…ごめん f(x) = cos x, α = (2m - 1)π, β = 2nπ とかは？ 長レス連発でスマソ
そろそろ切り上げるべきなんだろうけど幼女側の4人合わせたボタンの総ボタン押下回数25回で勝利できる方法見つけたので書いてみました
中々面白いパズルでした
名作だと思う
以下幼女4人と悪魔を合わせて参加者と呼ぶ
4人の幼女には0〜3の番号をあてがい幼女0〜幼女3と呼ぶ
ボタンの点灯でシグナルを送る事で各参加者は繋がる部屋に信号を送れる
各回線には0〜15の整数値aを割り当てコレを回線番号と呼ぶ
ここで回線aが幼女nが利用できるのは⌊a/4⌋≡n ( mod 4 )のときとし、その回線番号を幼女nの専用回線番号と呼ぶ
最初のチャネルから数えてt回目のチャイムと共に点灯する信号をt回目のシグナルと呼ぶ
幼女はあらかじめ設定されたデータ送信期間中に高々1個のシグナルを送信する事でデータを送信する
データの送信期間は一連のフェーズの前のフェーズの最終送信時刻tとそのフェーズで送る自然数の最大値mで決まり送信期間は時刻t+1〜時刻t+16mである、ただし最初のフェーズではt=0である
回線番号aの送信期間t+1〜t+16mのフェーズで自然数dを送信する場合送信者は時刻t+a+16d-15で点灯するシグナルを送信するとする、すなわち各フェーズで送られる信号数は高々1個である
またシグナルを送らない事で“シグナル無し”もあり得るとする プロトコルは以下のように定められる
カッコの中がそのフェーズで送られる自然数の最大値である
幼女0交信開始フェーズ(1)
幼女1交信開始フェーズ(2)
幼女2交信開始フェーズ(2)
交信記録転送フェーズ1(16⁴)
交信記録転送フェーズ2((16⁴)³)
交信記録転送フェーズ3(16⁴)
交信記録転送フェーズ4((16⁴)⁴)
よって各フェーズの送信期間は
16×0+1〜16×1、
16×1+1〜16×3、
16×3+1〜16×5、
16×5+1〜16×(5+16⁴)、...
のようになる 幼女0交信開始フェーズでは幼女0が各回線に1を送信する
幼女1交信開始フェーズでは幼女1が各回線に、幼女0と名乗る送信者からの送信を一本だけ受信している場合は1を、そうでない場合には2を送信する
幼女2交信開始フェーズでは幼女2が各回線に、幼女0と名乗る送信者からのからの送信を一本だけ受信している場合は1を、そうでない場合には2を送信する
この３つのフェーズが終わった段階で各幼女は各ボタンの相手方が幼女であると確信できる回線を少なくとも２つ持つことができる
この回線を信頼できる回線と呼ぶ
自分の送信する全ての回線がその受信者から信頼されていない幼女を疑惑の底にあると表するとする
３つのフェーズが終わった段階で各幼女は交信記録簿を作成する
交信記録簿とは16進数の16ᵏの位に左からk+1番目のボタンに着信している交信の相手方の回線番号をおいた16進数4桁の非負整数(0〜16⁴-1)とする、ただし相手方未送信の場合はその桁に4×3+0, その他不正な回線(相手が自分の専用回線を利用している場合もこれに含める)には4×3+1を置くとする
コレはすなわち相手は幼女3、あるいはそれを騙る相手であるとみなす事に該当し、幼女3は特権的に全ての回線に番号4×3+0を使え、回線4×3+1を使う事はないとみなすと考えるとわかりやすい
続く2個の交信記録転送のフェーズでは幼女1,2の交信開始信号に従って以下のように交信記録簿を転送する まず幼女1,2のうち2人ともが交信開始信号送信のフェーズでともに信号2を送っている場合を幼女0が孤立している状態と呼ぶ
幼女0が孤立しているのは幼女0が疑惑の底にあるための必要条件である
幼女0が孤立している場合においては交信開始信号送信終了の時点で幼女1,2は共に幼女0を名乗る着信を2件受けており幼女1,2の互いの相手のチャネルを正しく断定できるから幼女0が孤立しているか否かを正確に判断できる まず幼女0が孤立していない場合には幼女1,2のいずれか一方で幼女0への信頼できる回線を持たない方は自分の交信記録簿を交信記録転送フェーズ1で他方に送信する
その後交信記録転送フェーズ2に他方から最大2個の交信記録簿を送られた方は自分のそれとをpackして交信記録転送フェーズ2で幼女0に送信し、送られてきていなければ自分の交信記録簿に1111₍₁₆₎を必要なだけpackしてその値+1を幼女0へ送信する
この送信を受けて幼女0は自分が孤立状態にない事を確認できる
この時幼女0はこの時点で最大3個の回線から交信簿を送信されてきているから同じ要領で自分のものと合わせて16進数16桁の数にpackしてその値+1を幼女3への信頼できる回線がある場合には交信記録転送フェーズ4にそれに転送する 幼女0が孤立している場合には交信記録転送フェーズ2の終了時点で交信記録簿が送られてこない事で自分が孤立状態にあると正しく判定できる
この場合には幼女1,2交信開始フェーズで共に2を送信しており、そのいずれかに幼女0は信頼できる送信チャネルを持つからそれに自分の交信記録簿を送信する
交信記録転送フェーズ4に幼女1,2は幼女3に既出の方法で最大3個の更新記録簿をpackして幼女3へ送信する ここまでの段階で大別して以下の３つの場合がある
(A) 幼女0が孤立している場合
(B) 幼女0が孤立していないが幼女0から幼女3への信頼できる回線がない場合
(C) 幼女0が孤立していないが幼女0から幼女3への信頼できる回線がある場合
(B)の場合、幼女0は疑惑の底ではない
疑惑の底にあり得るのは幼女1,2か3であり、幼女0は幼女0,1,2の3人分の交信記録簿を精査して以下のように処理していく
まず幼女0,1,2が悪魔から全く交信を受けていない場合、その限りにおいて幼女3が疑惑の底でありそれは交信記録簿から判断できる
その場合には悪魔がまだ義務を果たせていない事は明らかである
残るは幼女1または2が疑惑の底にある時であるがこれはこのケースでは起こり得ない
何故ならもし仮に幼女1が疑惑の底にあるなら他の幼女0,2,3が信頼できる回線を持てない相手は全て幼女1でなければならないが、今仮定により幼女0のそれは幼女3である
以上によりケース(B)においては後述の(1),(3)の状態であると確定する
(A)の場合プロトコルにより全ての幼女の交信記録簿が信頼できる経路によって疑惑の底たり得ない幼女3に集められておりこの場合も後述の(1),(2),(3)のいずれかの状態である事が確認できるが、これはやや煩雑な議論を要するので後述するものとする
(C)の場合も(A)の場合と同様である 以上の交信の後幼女3は
(1)孤立している幼女がいない
(2)疑惑の底にない幼女から悪魔へつながる回線を少なくともひとつ確定できる
(3)悪魔はまだ義務を果たしていない
のいずれかの状態である事を把握できる
(1)の場合幼女3は全幼女に同時に相手が確実に幼女であると判断できる回線のボタン２つを同時に押下するように指示すれば良い
(1)の場合においてはこの指令を2分以内に信号３つで全幼女に伝達する事ができる
(2)の場合はその回線の保持者にその回線を伝えその幼女にはそのボタンのみを、その他の幼女には(1)と同様の作業をする様に同じく2分以内に信号３つで全幼女に伝達する事ができる
(3)の場合は以降信頼できる幼女間えやた、た、や、やた、たの交信以外を全て禁止すれば良い
悪魔が義務を果たすには疑惑の底にないいずれかの幼女への回線のシグナルを送信しなければならない
この時点で(2)の状態に移行して幼女の勝利が確定する
特に幼女が勝利するまでのボタンの押下する回数は高々12+3+3+7=25回である ・交信記録簿の精査方法について
今各幼女と悪魔から信頼できる経路を伝って疑惑の底にない幼女3に伝達された場合を考える
いずれかの幼女が疑惑の底にあるか否かは交信記録簿から判断できるがいずれの幼女も疑惑の底にないのであれば前述(1)の方法で幼女は勝利できる
疑惑の底に幼女0がいる場合を考えるが他の場合も同様である
疑惑の底にある幼女0と悪魔の２つの送信記録を見る
この場合２つの交信記録簿において以下の状態が発見できれば悪魔への回線が特定できる
(要件1) 幼女i ( i = 1,2,3 ) が受信している幼女0の専用回線番号での回線番号がともに4×0+pのとき交信記録簿のボタンpの交信相手は幼女iでなければならない
(要件2) 幼女i ( i = 1,2,3 ) が受信している幼女0の専用回線番号での回線番号に4×0+pが現れるときいずれかの交信記録簿のボタンpの交信相手は幼女iでなければならない
(要件1)を満たさない交信記録簿があればその記録簿の作成者が悪魔である
実際もしボタンpの交信相手が幼女iでないならこの記録簿の作成者の回線番号4×0+pは他の幼女につながっていないといけなくなるがそれは幼女iの受信記録に矛盾してしまうからである
(要件2)を満たさない回線があればその回線の送信者が悪魔である
実際もしその回線を4×0+pとして２つの記録簿の作成者のどちらが悪魔でどちらが幼女0であろうとも幼女である方の回線番号は4×0+pではない、もしそうならそれは幼女0のボタンpの交信相手は幼女iでなければならないが仮定によりいずれの交信記録簿にもそのような記載がない 我々が示したいのは悪魔が回線開設時に幼女1,2,3に対して同一の回線番号を使用した場合必ず上の要件に違反する事象が発生する事である
今幼女0が幼女1,2,3と開いている回線の回線番号を4×0+1,4×0+2,4×0+3とする
悪魔は同一回線番号4×0+3を幼女1,2に割り当てる事はできない、でなければ幼女1,2についての要件2に抵触しないにはボタン3の交信相手にはその2人を両方割り当てなければならず両方を満たす事はできないのでどちらかについての要件1に必ず抵触する
同様の理由で同一回線番号4×0+0も不可能である
悪魔は同一回線番号4×1+1をこのうち2人に割り当てる事はできない
でなければ幼女2についての要件2に抵触しないにはボタン1の交信相手には幼女2を割り当てなければならず、一方で幼女1についての要件1に抵触しないにはボタン1の交信相手には幼女1を割り当てなければならず両方を満たす事はできないのでどちらかについての要件1または2に必ず抵触する
以上により交信記録簿を精査することにより悪魔が同一回線を３つ以上開設した場合には必ずこの検査で露見し、のみならず悪魔への回線を少なくともひとつ特定されてしまう□ ダメや、一か所間違ってる
もう1ビットいるかな
26分か 1-₂C₁/4+₄C₂/4²-₆C₃/4³+₈C₄/4⁴-₁₀C₅/4⁵+…
を求めよ >>916
1+₂C₁x/4+₄C₂x²/4²+₆C₃x³/4³+₈C₄x⁴/4⁴+₁₀C₅x⁵/4⁵+…
= Σ (1/2×3/2×...)(2/2×4/2×...)/(n!)²xⁿ
= ₂F₁(1/2,1,1,x)
= 1/√(1-x) pxᵐの形のはすぐ見つかるけどそれしかないのかな
q(pxᵐ)ⁿ = x
iff qpⁿ = 1 , mn = 1
n = m-1, q = pnなら
m²-m-1 = 0, (m-1)pᵐ = 1
m²-m-1 = 0, p = 1/ᵐ√(m-1) >>918
元ネタはMichael Penn の動画？ スタートが左から順に1,2,..,(n-1),nと番号付いていて、ゴールが左から順にn,(n-1),…,2,1と番号付いたあみだくじがある。
このあみだくじの横線は最低何本か？ >>923
１とｎを横線で結び
２とｎ−１を横線で結び
・・・・
だからｎ／２でいいのでは 例えばn=4で1-2,2-3,3-4と繋いで1→4, 2→1, 3→2, 4→3
さらに1→3, 2→2, 3→1にするために3本いるからn=4だと6本じゃないの？ つまりi<jから辿っていってiとjがひっくり返る横線がひとつ必要でだからこのようなペア一個に対して横線一個が必要だから必要な横線数は最低でもn(n-1)/2
>>927の方法でn(n-1)/2本で可能だからこれが答えやな >>928
>ペア一個に対して横線一個が必要
それ直感過ぎ
iが左から右へjが右から左へ動く横棒が存在する証明が必要 それとその横線は他のk<lのための横線とは異なることの証明も必要 直感的には成立すると分かっても
これくらいは証明できよう？ だってi→σ(i)、j→σ(j)を結ぶpathで同じ横線通らなかったら位置入れ替わるわけないやん？ >>930ひとつの横線通る人高々2人しかいませんがな 中間値の定理のたぐいを使うかも
あるいはジョルダンの定理 >>932
これの証明が必要だと思うんだよな
>>933
これも帰納法か何かで証明するかも まぁ証明するなら上の方で出てた中間値の定理なりなんなりでi→σ(i), j→σ(j)は共有点を持たねばならない
もし共有点が縦線上の横線上でないところならそこから辿ってi=jで矛盾
よって共有点は横線分の閉包上
横線の両端点以外で共有点持ってる事が目標だけどA-Bが横線でAが共有点、縦線が上からX-A-YとしてどちらかがX--A-B、どちらかがB-A-X、いずれかにしても横線の両端点除く部分を共有する {1,2,…,n}の２元部分集合{i,j} (1≦i<j≦n)が置換σ∈S_nに関してねじれペアであるとは、
σ(i)>σ(j) が成り立っていることを言うものとする。
また、ここではあみだくじを置換と同一視する。
初期状態として何も横線が引かれていないあみだくじAに対し、既に引かれているどの横線よりも下に横線を追加するという操作を繰り返す。
この時、あみだくじAに関するねじれペアは、各操作ごとに高々１つしか増加しない。
一方、ゴールが左から順にn,n-1,…,1となっているあみだくじBに関するねじれペアは n(n-1)/2 個存在する。
したがって、Aにいくつか横線を引いてBにするには、少なくとも n(n-1)/2 本の横線を引く必要がある。 任意の関数は偶関数と奇関数の和に一意に分解できることを示せ (f(x)+f(-x))/2+(f(x)-f(-x))/2 f(x)=偶(x)+奇(x)とおくと
(f(x)+f(-x))/2=偶(x)
(f(x)-f(-x))/2=奇(x)
と計算されるから 実関数 f(x)=x を有限個の周期関数の和として表すことは可能か。 >>943
f(x) = tan(x) (x≠nπ/2), 0 (x=nπ/2)
って有界だったのか 問題の意図がわかりにくかったら申し訳ない、定義域は実数全体 レス数が950を超えています。1000を超えると書き込みができなくなります。
