JOI 2007 春 2-3 SALT TREE XV 証明付き解説

(個人的には珍しく) まじめに証明を書く．

2 人のプレイヤーが交互に，木に対して次の操作を行っていく．

操作ができなくなった方が負けである．

先手に必勝法があるので，それを実装せよ．(インタラクティブタスク)

相手の手番に回すとき，(頂点の数, 辺の数) = (偶数, 偶数) となるようにする．

今，(頂点の数, 辺の数) = (偶数, 偶数) の場合，1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできないことを示す．

よって，(頂点の数, 辺の数) = (偶数, 偶数) の場合，1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできない．

今，(頂点の数, 辺の数) = (奇数, 奇数) の場合，1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできることを示す．

辺の数が奇数であることから辺は少なくとも 1 つ存在し，葉が少なくとも 1 つ存在する．この葉を選べばよい．

よって，(頂点の数, 辺の数) = (奇数, 奇数) の場合，1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできる．

今，(頂点の数, 辺の数) = (偶数, 奇数) の場合，1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできることを示す．

辺の数が奇数であることから辺は少なくとも 1 つ存在するから，この辺を選べばよい．

よって，(頂点の数, 辺の数) = (偶数, 奇数) の場合，1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできる．

今，(頂点の数, 辺の数) = (奇数, 偶数) の場合，1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできることを示す．

すべての頂点の次数が奇数だと仮定すると，頂点の数が奇数であることから，次数の総和が奇数となるが，これは (次数の総和) = (辺の数) × 2 と矛盾する．
すなわち，次数が偶数の頂点が少なくとも 1 つ存在するから，それを選べばよい．

よって，(頂点の数, 辺の数) = (奇数, 偶数) の場合，1 回の操作後に (頂点の数, 辺の数) = (偶数, 偶数) にできる．

木において (頂点の数) = (辺の数) + 1 であるから，頂点の数と辺の数の偶奇は異なる．よって，最初の状態では (頂点の数, 辺の数) ≠ (偶数, 偶数) である．

以上の 4 つの証明より，相手の手番を常に (頂点の数, 辺の数) = (偶数, 偶数) にできるが，勝つためには頂点が 1 つだけ残っている状態で手番が回ってこなければならないから，相手は絶対に勝つことが出来ない．

N ≦ 2,000 より O(N²) が間に合うので，実装は雑でよい．