別冊数理科学 - アルゴリズムの道具箱

図書館で借りて。

なんかやたら簡単な気が。ていうか書いてるひと大丈夫なんかねって人が混じってる気がするんですけど。

なんて思ってたら後半の方はそれなりに面白かったです。前半もところどころ面白い部分もあるや。

ケーキを n 人で公平に分ける問題ってあるわけですけど、あれのとても難しいバージョンで、ケーキがイチゴだのチョコだのがゴテゴテ乗っているかもしれない任意のケーキで、参加者もイチゴが欲しいだのチョコはいらんだの任意の参加者なんですけど、その人々が全員不満を言わないよな切り方のアルゴリズムが1995年とかそのあたりに証明されたそうな。四色問題みたいな、まあそうだろうな、って内容を証明するのって想像できん。

ちなみにぐぐったらそれなりにそれっぽいものが出てきます。