基本情報
GM：Omni
PL：
|
+
|
レギュレーション等 |
- フルスクラッチ初期作成
- Dロイス1コ（PC1除く）
- Sロイス
- メモリールールを採用する
|
キャラクター紹介
PC1
|
+
|
追加Dロイス |
遺産継承者: メビウスの指輪
種別: 一般
効果: 裏・表のどちらも存在しない指輪。これを装着した者には強大な思考能力が与えられるという。
これの所持者は以下の効果を使用できる。また、このDロイスはロイスではなくユニークアイテムとして扱う。このアイテムは《完全獣化》の効果中にも使用できる。
<水星>
セットアッププロセスに使用する。そのラウンドの間、シーンに登場しているキャラクター2人の【行動値】を入れ替える事ができる。対象はこの効果を拒否可能。この効果は1シナリオに1回まで使用できる。
<金星>
あなたが装甲値によりダメージを10点以上軽減した場合、受けるダメージを-5する。ただし、この効果はあなたがカバーリングを宣言したとき失われる。
<地球>: [現在調査中]
[現在調査中]の判定の達成値を+30する。この効果を使用する度、[現在調査中]。
<火星>:
いつでも使用できる。シーンに登場しているキャラクターを好きなだけ選ぶ。選択したキャラクターの侵蝕率を-5する。
<木星>: 非活性
...
<土星>: 非活性
代償: [現在調査中]。侵蝕率基本値に+6する。また、この指輪の効果は進化し続けているが、それに伴い代償も大きくなる。この指輪に特殊能力が1つ追加される度に侵蝕率基本値を+2する。
|
PC2
PC3
|
+
|
設定等 |
一卵性双生児として生まれたが、研究用に【検閲により削除】に確保される。
姉は発症するも、彼自身は発症せず。
事故により姉は死亡、協力型レネゲイドビーイングによって弟は生き残り、UGNに保護される。
弟――創英はレネゲイドビーイングを姉――成智と思い込んでいる。
病み系シスコン。
|
PC4
|
+
|
基本情報 |
PL名：
性別：
linkプラグインエラー: URLを入力して下さい。[#ここにURLを挿入}
|
PC???
|
+
|
基本情報 |
PL名：
性別：
linkプラグインエラー: URLを入力して下さい。[#ここにURLを挿入}
|
コピー用
|
+
|
基本情報 |
PL名：
性別：
linkプラグインエラー: URLを入力して下さい。[#ここにURLを挿入}
|
キャンペーン情報
第1話『Let's play up!』
パズル難度について
★ 有名問題 時間をかければ解ける
★★ 有名問題 単純な操作で解けるが、凄く面倒
★★★ 正しい手続きに気づけば、時間をかけて解ける
★★★★ 難しい問題 ひらめきと根性が必要
★★★★★ 十分に才能と努力があれば、解説は理解できるかもね？
今回のまとめ
才能を認められ、プロップ学園に入学したあなた達。そんな所に謎の組織"ケトス・スブディティス"の副書記長"エリニュス"が現れる。そして、あなた達に対し、「あたし達はキミ達称号を持つ者に、パズルによる勝負を仕掛ける。そして、敗北という屈辱の中で死んでいくのよ！」と宣戦布告をし、一つの端末を渡す。
（「何でパズル解けないと屈辱になるんですか？」と真面目なツッコミを受けたが、反論ができないので無視された。）
そして、彼女が去った直後、教室の方で爆破が起こった。どうやら、これは組織の幹部"マーミン"の作ったパズルだという（Thm1）。
/ /「まさか、パズルの内容を少し見ただけで解法を見つけられるなんて。流石、称号を持つものだね。」
パズルで指示された場所に向かうPC達。そこには、レネゲイドの力で隠されていたものの、白い立方体構造の建物が存在していた。見た所、6～8階建てに思える。中に入ると、そこは外見よりずっと狭く、一辺が全体の1/8程度の部屋であった。そこは簡素な作りになっており、気になる点は四方の壁の扉と上に繋がる梯子、そして床に大きく書かれた391という数字。全員が部屋に入ると入ってきた扉のロックがかかり、そして部屋のスピーカーが鳴る。話を聞くと、マーミンの作ったゲームを「協力者」と共に解けば、「協力者」を解放するのだという（Prop 3）。
注釈: ゲームのルールが話の内容に関わるので、重要な所だけを説明する。一言で言うと、通信ゲーム。PC達と「協力者」がそれぞれ自身のみが知る番号を与えられるので、ゲーム開始前に情報を共有し合い、勝率を高める事を目標にする。
ちなみに、勝率を1にしないと、「運悪く」負けてしまう。
そして、ゲームが開始し、協力者の新月藍妃とともにこれを攻略する。PC達はこのゲームを8/9の確率で解く方法を発見するも、「運悪く」1/9のパターンを引き、敗北する。
そして、その直後、マーミンは一つのパズルを出す。「30分以内に解けなければ、あなた達はこの建物の崩落に巻き込まれるでしょう。」とのこと。
（ここで2回目定例終了）
説明が終わった後、タイマーが動き出し、それと同時に藍妃と連絡が取れるようになる。パズルについて、最大値が507とある値付近のものであること、藍妃のいる部屋の床に378、PC達のいる部屋の床に391と書いてある事をヒントに、パズルの構造を掴む。
パズルの謎に気づく事ができたPC達、しかしそのパズルの難解さから手を進める事ができない。そんな時、ジャックは、藍妃に（無理やり）手渡された箱を思い出す。その箱を開けると、一つの、裏表の無い指輪が入っていた。ジャックがそれをつけると、急激に思考能力が上昇し、パズルの答えを素早く埋め始める事ができるようになった。
パズルを解き、扉のロックが解除される。藍妃のいた部屋はPC達と同じ構造をしている事から、この建物のどこかに彼女が閉じ込められていると考え、彼女のいるであろう部屋へ向かう。そうすると、マーミンが彼女のいる部屋の前で立っているのを発見する。どうやら、「このパズルの報酬はあなた達の命であり、彼女の身柄ではない」という事らしい。PC達は藍妃を助けるため、戦う事を決める。
戦いに勝利したPC達。倒れる寸前、マーミンは「パズルを解いたあなた達へのささやかな報酬」として、自身の持っていた組織の端末を渡す。
藍妃を救出した後、彼女が指輪を持っていた理由について話す。彼女はどうやら昔組織に囚われ、実験の材料にされていたそうだ。そして、組織から脱走する際に盗んだものがその指輪だという。また、彼女によると、その指輪は量産を目的としたものであり、彼女が盗んだものもそのサンプルの一つだそう。
第2話『Eve's original sin』
目の前の「海竜の臣民達」（組織の名前が言いにくいから改名した）の幹部を倒し、一息ついたPC達。そんな所で、黒野の友人「ラルフ・ボラン」から一通のメールが届く（Q6）。メールの内容は不審なもので、それが助けを求めるものであるとPC達は気づく。
さらに、黒野以外の人たちには謎の人物「イブ」からのメールが届く（Q7）。しかも、メールの送信時間が「明日の12時」になっていた。暗号を解くと、「LemmaBldgFourthFloor」と書かれていた。ちなみに、ジャックが暗号を「Hey guys, we have a gift for you!」と間違えて解読した挙句、メールに添付された「computervirus.exe」のファイルを開いた理由は不明である（ファンブル）。
そして、そんな話をしている間、称号"ロベスピエール"の持ち主が学園の一員としてこの部屋にやってきた。どうやら、彼は今まで牢獄に囚われていたらしく、そこから肉体を救出するのに時間がかかっていたらしい。
メールの件を解決するため、ビルの2階、4階へ行く班の二手に分かれ、探索をする事となった。
4階では"イブ"という女性があなた達を待っていた。どうやら、彼女は「海竜の臣民達」の一員であるが、組織の情報をより知るため、あなた達と協力を持ち掛けたようだ。しかし、彼女はPC達の実力を試すため、1つのパズルを出題する（Q10）。解答時間は、PC達が息絶えるまで。（本当に協力する気ある？）
パズルの答えを見つけ、イブを捕まえたPC達。イブは協力の証として、「組織の書記長は、『新月藍妃』を殺す事を目的とした計画を立てている」事を教える。そして、彼女は連絡先を渡し、最後に「私の称号の由来、分かった？」と言い部屋を去っていく。
そして、藍妃はジャックに対し、「私が彼らに殺されるより前に、書記長を殺してくれないか」と頼む。
（追伸: 称号"イブ"の語源は盗聴者「eavesdropping」より。彼女は暗号パズルを得意とする。）
一方その頃、2階の方では。繁盛したラーメン屋の奥で友人ボランが座っていた。しかし、どうやら彼は偽物であり、本物の彼はこのビルの13階に囚われているという事が判明する。そして、彼を助けるためにはパズルを解けと言われる（Q9）。
説明を終えた後、「まずはこの部屋のトラップを耐えてみせてよ」と言われ、そして周りの人々が襲い掛かってくる。しかしその瞬間、ラーメン屋の店員「春日恭二」が大声で「待て！」と叫び、そしてPC達の元へ近寄ってくる。
どうやら、「このパズルが解けなければ、強制的にFHへ招待する」とのこと（Q8）。それを難なく解かれた春日は、報酬として2人を護衛を行う事となる。
（ここで4回目定例終了）
今回の問題
1話: Q1～Q5
Thm 1 ★3
問題
以下の陣は爆弾を仕掛けた25か所の教室に対応している。例えば、左下のマスは1階の1年一組の教室、左上のマスは5階の空き教室というふうにね。それぞれの部屋には、ある規則でAからYのアルファベットが対応している。実際にどのように対応しているかは、教室に入ってみたら分かるかもね？最後に、「総和は65」という事を伝えておくよ。では、20分後また会おう。
|
+
|
解答 |
各マスのアルファベットは数字の1～25に対応している。後は魔方陣のルールに従うだけ。
丸に入るのは12、15（重複）、16なので、アルファベットに直して（順番を変えると）pool。
|
解答は省略する。総和は簡単に求まるので、それを頼りに計算せよ（人間がやるなら、電卓は欲しいかな）。
Prop 3 ★5
問題
以下のゲームに勝利せよ
P.S. LaTeXをWikiWikiで使う方法か、pdfファイルの送り方を教えてほしい。
|
+
|
解答 |
P.S. これの名前はMarminの魔方陣（を元にしたもの）。
|
Thm 4 ★5
問題
上の問題を確率1で勝つ方法を求めよ。
（解答は上に内包されている）
Thm 5 ★4
問題
以下の[検閲済]の空白53か所を適切に埋めよ。
解答は来週公開の予定
|
+
|
解答 |
このパズルは8*8*8の魔方陣であり、最初に見せた魔方陣はその断面である。
（本当はその立体魔方陣をここに貼りたかったが、ExcelをラガWikiに載せる方法が分からなかったので断念）。
参考文献として、ネット上にあるslideshareというサイトの「立体魔方陣、多次元魔方陣の一製法」に書かれたものを用いた。これを参考にし、8*8*8魔方陣を構成している。
|
2話: Q6～
Prop 6 ★2
問題
ひさしぶり、最近調子はどう？
ひとりぼっちで寂しくしてたりしない？楽しくやってたらいいんだけど。
ひと見知りな所が昔からあったから心配かな。
さて、本題に入ろうか。
あした12時に、レンマビル2階の店でご飯を食べに行きたいんだ。
あしたの朝から少しの間、用事があって日本に行く事になったんだ。
あの時やり残した事もあったし、また一緒に話をしよう。
最後に。
ひまな時間があったら、その後キミの通ってる学校に行ってもいいか？
ひとりで時間を潰すのも少し退屈だからさ。
ひづけが変わらないうちに返事をくれたら嬉しいな。
|
+
|
解答 |
縦読みすると、頭文字がモールス信号の形式になっている事が分かる。メッセージはSOS。
|
Prop 7 ★3
問題
A*ril **h, 1*84. L*st night t* the f**ks. **l war f**ms. **e very *ood **e of a **ip f*ll *f *efuges being *ombed so**where *n t*e Mediterranean. A**ience m*ch *mused by s**ts ** * great h*ge f*t m** try*ng to s**m a**y w**h a h*licopter a*ter h**. First y*u **w h*m wallowing **ong in t* w*ter l*ke * po*poise, then *ou *aw **m th*ough the he*icopters g**sights, the* h* was f**l ** h**es and **e **a r**nd h*m t**ned p*nk and he sank as suddenly as though the holes had let in the water.
（文の最期に*3つ、スペース、*6つ、スペース、*3つ）
先に検閲しておいたわよ。
イブ
|
+
|
解答 |
黒塗りになっている部分は「1文字が黒塗り」「2文字が黒塗り」の2パターンのみ。これは、1文字が黒塗りになってる部分を・、2文字が黒塗りになっている部分を―と解釈したモールス信号となる。また、休符として「黒塗りが無い単語」を採用している。読み解くと、LemmaBldgFourthFloor。
参考: 黒塗り世界宛て書簡
|
Prop 8 ★1
7人の小人が発言を行う。1人だけいる正直者を当てよ。
赤「自己複製を行わない生物は存在するよ。」
橙「初夏の北陸地方には、山を通り抜けてきた風が吹いてくるから、フェーン現象により気温が低くなるよ。」
黄「無理数は√とπの事だよ。」
緑「同位体を持つ原子は硫黄、炭素、酸素、リンの4種類だよ。」
青「電流内の電子は光速の速さで動いているよ。」
藍「定木とコンパスを有限回使用しただけでは作図不可能な点は存在するよ。
紫「水は絶対に、丁度100度で沸騰するよ。」
|
+
|
解答 |
答え: 藍色の小人。解き方は、普通に問題を解くだけでよい。共通テストかな？
赤: 生物の（一般的な）定義に自己複製がある。
橙: フェーン現象によって、気温は上がる。
黄: √4は有理数だし、eは無理数。数学を舐めてるのかな？ねえ、ト〇イ。
緑: 同位体ではなく同素体。同位体は全ての原子に存在する。
青: 電子はそんなに早くない。というか、電子は質量を持つので仮に光速で動くと相対論に矛盾する。
藍: 真実。本当はここにその証明を書こうとしたが、それを行うためには幾つかの簡単でない前提知識が必要なので省略する。
概要だけ言うと、（最初に与えられた点が有理数として、）定木とコンパスで描かれた図形の交点は高々2次の方程式の解として表され、その係数が有理数となる事を用いる。この操作を1回行ったときに与えられる点は（有理数か）√nを含んだ点である（例えば√3）。逆に、高々2次方程式の解はa+b√cの形ですべて書ける。この操作を有限回繰り返した場合、例えば2^0.25等は作図可能である事がすぐに分かる。しかし、πやx^3=2の解等は上の操作を有限回行っても表現できない。よって題意は示された。
追伸: 厳密にx^3=2を満たすxが作図不可能である事などを示すのは難しい。これを示すには、例えば「拡大次数」という概念を用いる。群論とか体論とかでググれば必要な情報が出るはず。
ちなみに、「x^3=2は3次方程式で、2^n次方程式の解でないから作図不可能」とやったからといって証明は省略できない。というのもx^3=1やx^3=2√2の解は作図可能なため。
紫: 圧力等の条件を変化させると沸点は変化する。
|
Thm 9 ★4
鬼ごっこ。ルールは口頭でのみ説明するので、次週まで公開しない。
「ルールは単純。これは鬼ごっこよ。鬼は友人をタッチする、つまり捕まえたら勝ちよ。逆に、友人は鬼にタッチされずこのビルから脱出できたら勝ちって事だね。
大丈夫、キミが負けたとしても何も罰は無いから、気楽に解いてみなよ。
今、友人はこのビルの13階の一室に囚われている。同じ階の制御室にあるスイッチを押せばその部屋の扉は開いて、友人は外に出られるようになるよ。勿論、直接扉を壊しにいってもいいよ。
ちなみに、友人にはこのゲームのルールを教えているからその点については心配しなくていいよ。 」
|
+
|
解答 |
ちなみに、鬼はPC達。ルールはよく聞こうね。
P.S. 「彼には正しいルールを伝えた」とは言ったけど、「あなた達にも正しいルールを過不足無く伝えた」とは言っていないよ！
|
Thm 10 ★4
この部屋の中には、丁度1人の、本物のイブが存在する。本物以外は全員偽物である。
6人のイブが発言を行う。本物のイブと偽物のイブ達のうち、一方のみが正直者、もう一方は嘘つきである。正直者は必ず本当の事を言い、嘘つきは必ず嘘の事を言う。
（明示はしていないが、6人は誰が正直者か知っている。）
1「2のイブは本物よ。」
2「5のイブは正直者だわ。」
3「全ての植物は光合成をするわ。」
4「6に『本物のイブは正直者？』と聞いたら『はい』と答えるわ。」
5「私は本物よ。」
|
+
|
解答 |
答え: 喋っている6人の中に本物はいない。
解き方
まず、3は嘘つき（例えば「ムジナノショクダイ」は光合成をしない植物）
1が正直者とすると、2は本物かつ嘘つきとなるため、5は偽物かつ嘘つきとなるがこれは矛盾。ゆえに1は嘘つき。
1が嘘つきより、2は偽物となる。ここで1が本物と仮定すると、2、5は正直者となるがこれは4の発言に矛盾。
以上より、1と2は偽物かつ嘘つきと分かる。よって、2の発言より5も偽物かつ嘘つき。
ここまでの議論より4、6については少なくとも一方は嘘つきであるが、片方のみが嘘つきだとすると矛盾が生じるため両方とも嘘つき。ゆえに本物はここに存在しない。
|
Thm 11 ★4
ここには6人の人間がいる。彼らにはそれぞれ、「神」「悪魔」「天使」「大悪魔」「大天使」「人間」の役割が与えられている。彼らには以下の制約が課される。
イ) 大天使がそばにいないとき、大悪魔は天使を殺す
ロ) 大悪魔がそばにいないとき、大天使は悪魔を殺す
ハ）神がそばにいないとき、天使、悪魔、大天使、大悪魔は人間を殺す
二）円盤を操作できるのは神、大天使、大悪魔のみである。
2人乗りの円盤を8往復させて、神、悪魔、天使、大悪魔、大天使、人間すべてが無事に中央にまで来れたらゲームクリアとなる。
注意: 以下の解答にはファイ・ブレイン第2シリーズ18話のネタバレが含まれます。ご注意ください。
|
+
|
解答 |
まず、上のルールで説明していない点として、3往復目終了時に「悪魔」「天使」の役割を持った像が1つずつ現れることに注意せよ。仮にこのルールを3往復目までに気づかないとクリアは不可能になる。ちなみに、この像が無いと5手で終わる。
→で初期位置から中央への移動、←で中央から初期位置への移動を表す。最期の括弧は、中央にいる役割を示している。
1. →大悪魔、悪魔 ←悪魔 （中央: 悪魔）
2. →大悪魔、大天使 ←大天使 （中央: 悪魔、大悪魔）
3. →人間、神 ←大悪魔 （中央: 悪魔、神、人間）
4. →悪魔、大悪魔 ←大悪魔 （中央: 悪魔*2、神、人間）
5. →大悪魔、大天使 ←大天使 （中央: 悪魔*2、大悪魔、神、人間）
6. →天使、大天使 ←人間、神 （中央: 悪魔*2、大悪魔、天使、大天使）
7. →天使、神 ←神 （中央: 悪魔*2、大悪魔、天使*2、大天使）
8. →神、人間 （中央: 悪魔*2、大悪魔、天使*2、大天使、神、人間）
|
Thm12、13、14 ★3
問題（演出含）
あなた達は、この国の疫病を抑えるため旅に出る事になりました。この国が助かるためには、その疫病を国から払うしかありません。そんなとき、一つの信託が降ってきたのです。「3つの”天国”、その全てに巡礼せよ」と。このお告げを聞き、あなた達は旅に出たのです。
あなた達はこの円盤に乗り、3か所の天国を目指します。しかし、この円盤は以下で定められた場所以外に案内してくれません。
イ) 既に移動した場所
ロ) 既に移動した場所2つをP, Qと置いたとき、Pを中心としQを通る円、PとQを通る直線上の場所。ただし、その場所は何らかの手段で明示的に丁度1か所を指定しなければならない。
今、あなた達が移動できる場所は今いる足場と赤色のレーザーで示された2か所の点のみです。この2つの点は、どちらも丁度あなた達のいる場所から40m離れています。また、見て分かる通りその2点は大体70m離れています。
最後に、制限時間は30分です。もし制限時間を超えると、この国は疫病によって滅亡し、この空間を維持する事はできなくなります。
問題（簡単に言い換えたVer）
最初に原点O、40m先の点2つ（A、Bとおく）が与えられている。
Thm12 Oを中心とした半径40mの円上の、AとB（の角度）を3等分する点に移動せよ（作図せよ）。
Thm13 線分OA上にある、体積16000 m^3の立方体の一辺の長さを表す距離の点に移動せよ（OA上にある、Oから20*2^(1/3)だけ離れた距離の点に移動せよ）
Thm14 線分OB上にある、半径40mの円と同じ面積を表す正方形の一辺の長さを表す距離の点に移動せよ。
|
+
|
解答 |
Thm13 問題文の条件より、与えられた2点の中点を取ることはいつでも可能である（その2点を半径1上の点とし、角度をそれぞれθ, φとおく）。その中点と半径1の円の交点を結ぶ事により角度(θ+φ)/2の点は作図可能となる。ゆえに、以下を行えばよい。nは必要な近似精度に合わせて選択せよ。
（1/3=1/2+1/8+1/32+...に注意）
float θ = 0;
float φ;
for(i = 0; i < n; i ++){
φ = (θ+φ)/2;
θ = (θ+φ)/2;
}
Thm14、15も、13と同様に近似を行えばよい。近似の方法はいくらでもあるが、一番直感的なものは2進数展開であろう。S={1, 2}としたとき、n回の中点を取る操作で小数点n桁までの値を作図可能である。ゆえに、元の数を十分な精度で2進数展開すればよい。（同様の手段を取る事により、任意の実数は作図可能となる。一般的に知られた事実と異なる結果が得られた理由は、無限操作を許したためである。）
（一般の場合の解答）
/ Xの近似を行う。xをXの整数部分、y=x+1とおく。nは近似精度に応じて決定せよ。
float a = x;
float b =y;
for(i = 0; i < n; i ++){
float c = (a + b)/2
if(X < c){
b = c}
if(X >= c){
a = c}
}
return a;
|
3話 Prop16～
Prop16 ★1
この映像は4つの球体がある法則に従って動いている。この運動は以下で指定した条件におけるメタン分子の運動に等しいか？
（温度、初期配置、環境との相互作用等についての条件）
ただし、「必ず正確に動く、計算能力を無限と仮定してよい古典コンピュータ」を使用してよい（予め使用しそうなプログラムは記入している）。
|
+
|
解答 |
古典コンピュータに与えられた物理法則と初期条件を代入し、適切な許容誤差の元で実行すればよい。ある意味では難しいが、複雑性クラスの考えの元では問題として成立してない。何故なら、コンピュータの出力を信用する事ができるから。
これを複雑性クラスAMの問題として解釈するなら、「NO出力のとき、”どんな”アルゴリズムに対しても高い確率でNOと出力できる」（健全性）という条件が必要である。ちなみに、この問題を（適切な設定の元で）AM問題と解釈できるかは確かめてない。でも、量子ハミルトニアンの問題は大体QMAで、かつAMはQMAより大きいクラスだから多分大丈夫。
|
Prop17 ★2
ここには256枚の金貨と、1つの天秤がある。あなた達はこの金貨の中に偽物の金貨があるかを調べる必要がある。偽物の金貨は本物と少しだけ重さが違い、全ての偽物の重さは同じであるという事だけが分かっており、天秤を適切に用いるとその違いを測定することができる。天秤は何回でも用いてよい。
もしこの256枚の中1枚でも偽物があれば、偽物の金貨全てを「廃棄箱」に入れよ。逆に全て本物であれば、全ての金貨を「銀行箱」に入れよ。
<知覚: 6>見た目は組織の身分証として使われているコインと同じである。
|
+
|
解答 |
金貨を2分割し天秤に載せる。このとき、天秤が傾く事は偽物の金貨がある事の十分条件である。また、天秤が傾かない事は偽物の金貨が使用したグループに偶数個あり、かつ双方の皿に偽物の金貨がそれぞれ同数ある事と同値である。
ここで天秤が傾かなかったときは、片方の皿にある金貨を取りそれを2分割し同様の操作を行う。途中で天秤が傾いたとき、操作を止め「偽物がある」と判断する。
というのが一つのやり方である。しかし、上のやり方では「偽物の金貨が0枚か256枚全部か」を判定できない。この判定を行うには、本物と分かっている金貨が必要である。
ちなみに、今回のパズルでは偽物の金貨は256枚とした。
P.S. 計算量はO(log n)、複雑性クラスはP
Note: このパズルについて、「高確率で偽物の金貨の存在を判定する」と言い換えたらどうか。直感的には、偽物の金貨があるのに天秤が傾かない確率は低そうである。実際、偽物の金貨の枚数をkとして、これがランダムな値をとるとき、3回上の操作を行ったとき天秤が一度も傾かないのはkが8の倍数のときのみなので、最大でもエラーの確率は1/8である。しかし、kの値が事前に固定されており、確率に左右されるのはそれぞれのコインを左右の皿どちらに置くかという点のみだとする。このとき、k<<nと仮定すると、kが2^（操作回数）の倍数のとき、うまく判定できる確率は定数で抑えられる。実際、nが十分大きいとき、偽物の金が2枚のときに天秤が傾かない確率は1/2、偽物の金貨が4枚のときに天秤が傾かない確率は3/8である。
偽物の金貨の枚数が少ないときは発見率が低いが少ない回数で偽物の金貨の発見率が1にあり、一方で枚数が多いときは発見率が高く、少ない回数では偽物の金貨の発見率は1にならない。この関係があるため、実際に上の操作を行えば上の計算より早い段階でエラー率が0に近づく。
|
Prop18 ★4
ここには256人の人間がいる。この人間たちは「正直者」と「嘘つき」のどちらかに属しており、ここにいる人間たちはお互いがどちらに属しているかを正確に理解している。そして、ここにいる人々は幾つかの文章を発している。
このとき、以下のルールを満たしうるかを判定せよ。満たすなら、扉のパスワードは「嘘つきの人の番号を小さい順に埋めたときのもの」、満たさないなら「0」である。
- 「正直者」は常に本当の事を言い、「嘘つき」は常に嘘を言う
例: 1人目が「私は嘘つきである」と言った場合、上は満たさないので、パスワードは0。
P.S. 作問意図について（問題部分）
n人の人間がそれぞれ幾つかの文章を持ち、その合計はp(n)である（p: nの多項式）。a番目の人が正直者であるときx_a=1、嘘つきのときx_a=0と解釈するとき各文章はx_1からx_nについての論理和として書くことができる（要証明）。このとき、出力1を「条件を満たす」と解釈する。求める問題はF(x_1, ..., x_n) = （p(n)コの文章の論理積）に対してF(x)=1を満たすxが存在するか？というものである。
ちなみに、例の1人目が「私は嘘つきである」と言った場合については、xが1人目の状態を表すとき、この文は以下のように表される。
f(x)=(x∧(¬x))∨((¬x)∧x) = 0
また、xが「yとzは両方とも嘘つきである」と言った場合については、以下の通り。
f(x, y, z) =(x∧(¬y)∧(¬z))∨( (¬x)∧¬( (¬y)∧(¬z)))
|
+
|
解答 |
実際の文章は登場PCしか知らないので、ここで解答を語る事はできない。多分、YES出力のうち解答が一意に定まるような問題が出題されている。
P.S. 作問意図について（解答部分）
この問題はm-SAT問題として解く事ができる。ゆえにこの問題の複雑性クラスは高々NP（mは3以上定数以下と仮定した）。各文に対してmがいくつになるかは演習問題にする（GMが解けなかったため）。
追記: 一般の論理式の形がリテラルの積に書けるかは簡単に示せないので、一旦その部分は取り消しておく。
|
Prop19 ★3
ここには2つの点と線で描かれた絵がある。一見すると2つの絵は異なるように見えるかもしれない。しかし、「点と点の距離」は自由に変更してよいという条件の下で2つの絵は同じか？ただし、点と線の数はどちらも同じである。
この問題を暗算で解くのは難しいので、部屋の中にあるコンピュータを使用してもよい。このコンピュータの計算能力はどれも十分高く、少なくとも一つのコンピュータは正確に動く事は確約する。
|
+
|
解答 |
この問題は以下のアルゴリズムを用いて解く事ができる。片方の絵（グラフ）をG、もう一方の絵をFとおく。
1) G、Fの点に1, ..., nと番号を振る。その後ランダムにGかFを選択する。選択した方をXとおく。Xの点の番号を入れ替えたグラフσ(X)を構成する。
2) σ(X)をコンピュータに入力し「σ(X)と同型なグラフはどれか？」という問題を解かせ、その答えを出力させる。
上のステップを行った場合、GとFが同型でなければ上のアルゴリズムは確率1でXを出力し、GとFが同型であれば”どんなアルゴリズムに対しても”確率1/2でXを出力する（この出力はG or Fの2通りなので1bitの通信で行える）。ゆえに何度か上の1),2)を行えばGとFが同型かを高確率で判定できる。注意として、σを直接コンピュータに送ったり、GとFに固定した順番をつけてはならない。前者は「σ^-1をかけたものを出力するアルゴリズム」、後者は「1番目のグラフを出力するアルゴリズム」に対して確率1でGを出力してしまうため。
細かい話を行うと、このProp19の解答は以下の通り。
全てのパソコンに対し、上のアルゴリズムを実行する。
1) GとFが"同じ"とき
上の説明より、Xと出力が一致する確率は"全てのコンピュータに対し"1/2である。よって、この操作を十分な回数繰り返せば、十分高い確率で全てのコンピュータが"GとFが同じ"という事を意味する情報を出力する。
2) GとFが"同じ"でないとき
上の説明より、Xと出力が一致する確率は、"正しく作動するコンピュータに対し"1である。よって、この操作を何回繰り返しても、少なくとも一台は"GとFは異なる"という事を意味する情報を出力する。
よって、上の操作を十分回数行い、「少なくとも1台が常にXと出力が一致する」ときに2つは異なると結論すればよい。
P.S. この問題はクラスIPの問題である。IPの定義は以下の通り。
1) If the answer is "yes," the prover must be able to behave in such a way that the verifier accepts with probability at least 2/3 (over the choice of the verifier's random bits).
2)If the answer is "no," then however the prover behaves the verifier must reject with probability at least 2/3.
（Complexity zoo, https://complexityzoo.net/Complexity_Zooより引用）
|
Thm 20 ★5
It was a bright unhot day, I eated the apple though she regarded it as crimethink. Thinkpol comed to me to arrest ungood person. The ungood room was surrounded, it was easier to have one qubit store the definition of Turing machine than escaping from here. I remembered the days of watching prolefeeds, which was doubleplusgood products, so I feeled sad.
In the last time, though it was thoughtcrime, I would say that war is not war, and freedom is not freedom. We must reduce the entropy; if we don't, the world speedwise will shrink and only something “DUCKSPEAK” will remain.
It is not bad that a man convinces himself that geocentric theory is correct; it is bad that he never accepts some witness which show that the earth is not the center, and firewise believe Minitrue. The mans must think whether Ingsoc, or government control your vocabularies, the fundamental ways to speak to others, and you must use many words and scientific terms. Once your vocabulary shrink, it is difficulter to think something clearly; for example, for the people, who use a word “duckspeaker” when he praises the speaker and curse them, it is unpossible to hold own opinion about the speaker. It is one way that we use the term of classical physics as basic vocabulary, not to unincrease those and help you think cleanwise. I want you to think and tell your own thought sunwise, and think about Minipax, though it’s only a cryptologist’s selfish talking. Finally, I’m glad to see “Turing”, she gives me this lightwise fate so I present one puzzle in recursively enumerable laungage. I wish that you happy to solution this puzzle with oldthink. Please tell me some impression about the query of this complexity theory problem after you solve enjoyful one and recall ungodful me. I say goodbye, with the linguistics and cryptography puzzle; I hope you are happy, in joycamp.
最終更新：2024年06月20日 21:22
