なお、同じ内容ならば、簡潔なレポートに高得点がつきます。
ただし、説明不足、特に設問８に関して私が理解できない
（あるいは余りに漠然としている）ものは減点です。
（1）
Stirlingの公式（数学辞典、数学公式集、
解析概論（高木貞治）などに有ります）を使って，
100N^2 から50N^2 を取り出す組み合わせ数
がほぼ(π/2)^{-1/2} 2^{100N^2+1} (10N)^{-1}
であることを示しなさい。
（2）
アリスもボブも破産していない確率に
2^{100N^2} を掛けたものは、上記の組み合わせ数の２N倍よりも
小さいことを示しなさい。
（3）（1）と（2）から命題が証明できます。
ヒント：正しいレバー位置にしたら1円もらい、レバー位置を 誤った方向に動かした時1円払うと考えてください。 問題4の結果（破産までの回数の期待値がN^2であること） を用いてよろしい。
「どちらか一方は正しい位置にありません」というのは、 私は「両方間違った位置にある可能性も有ります」という つもりでした． これは設問の説明が悪かったようで，「一方だけ間違っている」 という意味に採った人が多かったです（それでも減点はしません）。 正確な評価をしたほうがいいのですが，易しい評価を しましょう。
まずランダムにレバーを引きます。
間違っているレバーの数をXとします。Xの期待値は１０で、
Xまたは２０−Xは１０以下です。
その後、提示された対のどちらかを変更すると、
間違っているレバーの数が１増える確率が1/2以下で、
１減る確率は1/2以上です（もし、「一方だけ間違っている」
だと、確率はちょうど1/2になります）。
これはコイン投げゲームと同じです。
だから、200回やると、
全部正解になる確率が（1/2)(1-X^2/200)以上
（マルコフの定理から
間違っているレバーが０になるか、２Xになるかどちらかになる
確率が1-X^2/200以上、０になっている確率がその半分）
になります。
マルコフの定理の変わりにチェビシェフの定理を使うと
もっと正確に議論できますが、ちょっと難しい。
200回操作して、空かなかったら初めの配置を逆転して
やり直して見ましょう
（こうするとXを２０−Xに置き換えたことになります）。
これで空かない確率は上の議論からだけだと1/2以下です。
きちんとやるともっと小さいです。
駄目だったら，これを何回もやり直します。
期待値評価は、この議論だけだと800以下である
ことになります。
「どちらか一方だけ間違っている」モデルで、 魔法使いが対を提示しないまでレバー操作を行って， 駄目だったら全部逆にすればよくて、期待値は110、 というような答案が多かったです. 概略はOKです。
充足問題（SAT）は授業で聞いたことがあると思いますが， ２充足問題（２SAT)とは、ブール変数x_1, x_2,...x_n と、ブール変数もしくはその否定の対の集合 C_1, C_2,....,C_m が与えられます。 対C_i=（x,y)において、xまたはｙが1になれば、この対は 充足されるといいます。 全ての対が充足されるようにブール変数に0，1を割り当てる解 （充足解）を求める（あるいは、存在しないことを示す）のが ２SAT問題です。
今，２SAT問題が与えられた時，一つの充足解の 変数割り当てAを考えましょう。これが魔法使いの部屋 をあけるレバーの配置です。 最初にある割り当てを行った時， 充足されていない対を一つとります。 この対に入っている変数2つのうち，どちらかはAと異なる 割り当てになります（Aではこの対は充足されていますから）。 つまり、この対は「魔法使いが示す対」になります。 ですから、もし充足解が存在すれば、 O(n^2)回の操作で、「扉が開く」、すなわち ２SAT解が求まりますし、もしも扉が開かなければ，高い確率で， もともと充足解が存在しないということが言えます。
さて、中村真輔氏のレポートでは、次のような考えが示されています。
全部でレバーの組み合わせの数は２の20乗です。
1つの対が示されたとき、その対の８通りの可能性のうち、現在の
可能性が否定されます。ですから、残りの3通りの
一つになります。
よって、残る可能性は7/8倍になります。
従って，ｋ個の対が示されたとき、組み合わせ数は
(7/8)^k 2^{20}になります。k=103だと、これは１以下になるので，
103回魔法使いの出す対を見ると、
高い確率で組み合わせは1通りに決まります。
従って、後20回で、計123回
レバー操作をすると扉が開きます。
これは実は正解（厳密には、魔法使いが可能な対からランダムに
選んで示すという条件が要り、また、それでも正確では
ないのですが）です。
意表をつかれましたが、出題者（私）の「負け」です。
問題を「レバー操作の数」と書いたのが、かなり迂闊でした．
問題の本質（NPとは何か、情報の公開とは何か、複雑度とは何か）
をついているので、私はこういう意見が好きです。
これが「私の意図した正解」、すなわち、「高速に扉をあける方法」
だと1億円もらえます。私が意図した解と
どこが違っているのでしょうか。
問題は，最後の20回でどちらにレバーを引いたらいいかを
「考えないと」いけない事です。今まで見た103回の
魔法使いの「提示」から、最後の20回のレバー操作を
するための情報は開示されているのですが，どうやって
具体的な操作をその情報から「発見する」事ができるのでしょうか。
世の中である「公開鍵暗号」などは、上のような
「公開されている情報」から「具体的な操作」をするのが
難しい場合があることを用いて設計されています。
実際，上の例では、103個の提示対
は、３充足問題の「問題」を与えたことになります。
そこから具体的なレバー操作を計算するのはNP完全なので、
レバー操作の数は確かに123回ですが、最後の20回を
どう操作をするかを３充足問題を解いて計算しないといけません。
理論的には太陽が燃え尽きるくらい計算しても答えが出ません。
でも、３充足問題はこれくらいのサイズだと、ヒュ-リスティクス
と呼ばれる手法で割と早く解ける場合もあるので，
魔法使いの部屋の前で，超高速コンピュータを持っていれば、
中村さんの解が賢い場合が多いということになりますね．
この中村さんの議論を精密化すると、
「３充足問題の問題例生成」という、最近はやりの研究テーマに
行き当たりますし、
SATを用いた公開鍵暗号ができるかもしれません。
一方、O(N^2)で「扉が開かない」場合は， 高い確率で「もともと交差しない配置は不可能」ということが 判定できます。