情報システム評価学’00レポート問題

問題１

平面上に線分の集合が有ります．これらはM箇所で交差しています。 線分を赤と緑に塗り、同色の線分間の交差をM/2以下にすることが 必ず出来ることを示しなさい。ただし、各交差点ではちょうど2本 の線分が交差していると仮定します。

問題2　

アリスとボブがコイン投げゲームをするとします。 表が出ればアリスが勝ち，裏が出るとボブが勝ちで、 負けた方が勝ったほうに1円払うとしましょう。 最初にアリスもボブも N円持っており、どちらかが破産するまでゲームを続けるとすると、 （N / log N）^2 回まではゲームが続く確率が高いことを チェルノフの定理を用いて示しなさい。

問題3

上の問題で， 100N^2回でどちらかが破産している確率は1/2以上です。 これを次のようにして示しなさい。
注意：　他の方法（問題4の結果を証明なしに使ってはいけません） で示した場合は、いい点をあげます。

（1） Stirlingの公式（数学辞典、数学公式集、 解析概論（高木貞治）などに有ります）を使って，
100N^2 から50N^2　を取り出す組み合わせ数 がほぼ(π/2)^{-1/2} 2^{100N^2+1} (10N)^{-1}　 であることを示しなさい。
（2） アリスもボブも破産していない確率に 2^{100N^2} を掛けたものは、上記の組み合わせ数の２N倍よりも 小さいことを示しなさい。
（3）（1）と（2）から命題が証明できます。

問題4

問題2，3で、 実は破産までの回数の期待値はN^2です。 （だから、１００N^2は過大な評価です）。 Motowani-Raghavanの本の第6章に、 エレガントな解法がありますが、 授業ではやっていません。 シミュレーションプログラムを作って，これを確かめなさい （もしくは、徳山が間違っていることを示しなさい？！）。

問題5

魔法使いの部屋の扉には２０個のレバーが有ります。 各々のレバーをONかOFFにして、全部が［正しい」位置に 来た時に扉が開きます。 扉にはこんな文章が書いてあります。 「扉が開かない間は、2つのレバーの対が示されます。 どちらか一方は正しい位置にありません。」　 何回くらいのレバー操作で扉は開くと思いますか?

ヒント：正しいレバー位置にしたら1円もらい、レバー位置を 誤った方向に動かした時1円払うと考えてください。 問題4の結果（破産までの回数の期待値がN^2であること） を用いてよろしい。

問題6 （これは難しいResearch　Problemなので、 無理にレポート期間中に解こうとしないように）。

文章が 「扉が開かない間は、３つのレバーの組が示されます。 そのどれかは正しい位置にありません。」　 だったらどうでしょうか？

問題７

　 ｎ対の平面上の線分があります（全部で2ｎ本）。 各々の対から1本づつの線分を選択して， 選んだｎ本の線分が交わらないように 出来るかどうか（高い確率で） 判定するアルゴリズムを考えてください。
ヒント：問題5を使います。すこし考える必要のある問題です。

問題８

自分が興味を持っているコンピュータ科学の問題に付いて 徳山にわかるように説明してください。