2015年12月18日

日記

『完全なる証明』にラムゼー問題の解き方のさわりが書かれてたので解いてみたんだが、すんげーごちゃごちゃしてて「こんなんだっけ?」とか思ったんだが、『放浪の天才数学者エルデシュ』見るとエレガントな解放が・・・(普通にネット検索すれば出てくるけど) こんなエレガントな証明を忘れるなんて、そもそも理解できてなかったってことなんだろうけど、これで理解した。 まぁ、こういうのの繰り返しだねぇ。 ところで、よく例に出されるラムゼー問題は「6人のうち全員知り合いか全員知り合いでないかの3人が必ずいる」ってやつだけど、3人じゃなく4人の場合にこの証明を拡張するってのはどうするんだろう。 あんまり簡単にはできなさそうだね。

そう言えば知り合いか知り合いでないかの2択ではなく、3択(どう例えればいいのかな?血縁関係とか?)にするって方向の拡張とかはどうでしょう?

ふと、このラムゼー問題って「井に○×を書いていって3つまっすぐに並べたら勝ち」みたいなゲームと同じようなことができるんじゃ?と思ったけど、既に「ラムゼーゲーム」ってのがあるようで。 これ、実装するといいプログラミング演習になりそう。 誰かやって。

完全なる証明―100万ドルを拒否した天才数学者 (文春文庫)

完全なる証明―100万ドルを拒否した天才数学者 (文春文庫)

文庫 放浪の天才数学者エルデシュ (草思社文庫)

文庫 放浪の天才数学者エルデシュ (草思社文庫)


ツイート (ツイート数 27)