入試数学で過去最難問とか言われてるとnuc さんとこに書いてあったのでやってみた。(問題文は link 先とか Google 先生にもらってください。) 噂通り難しい…何度も中断するハメになったので正確にはわからないけど、たっぷり 10 時間は使ったと思う。その後、河合塾の解答例を見たら同じ方針だったけど、河合の解答は一番肝心な所 (白から到達可能と黒から到達可能は排反) の証明をしてなかったので、吹いてしまった。 なお、この blog にもっと美しい解法が載っている。こういうセンスのいい証明がサラリとできるようになりたい。Link 先の解法は、白だらけの可能グラフの各ノードに UID を振ってそれぞれが誕生した瞬間を分析すればいいですよというお話。その際、問題の形を一元化するために両端にノードを補完しているのが見所。 でも、河合の解答を補完したものはパッと見、見当たらなかったし、白からの