MathLabs

第5問

リス Bushy と Jumpy は冬に備えて 20212021 個のクルミを集めた。Jumpy はクルミに 11 から 20212021 まで番号をつけ、お気に入りの木の周りに円形に 20212021 個の小さな穴を掘った。翌朝、Jumpy は Bushy が各穴にクルミを一つずつ入れたものの、番号を気にしていなかったことに気づいた。不満に思った Jumpy は、20212021 回の操作からなる手順でクルミを並べ替えることにした。kk 回目の操作では、Jumpy はクルミ kk に隣接する二つのクルミの位置を入れ替える。ある kk が存在して、kk 回目の操作で入れ替えるクルミ aa と bb が a<k<ba<k<b を満たすことを証明せよ。
ステップ 2/5: 処理された順にクルミを赤く塗る
ざっくり言うと

どのクルミが既に「使われた」かを色として記録すると、交換の過程が純粋に組合せ論的な彩色問題になる。

colour walnut k red right after move k\text{colour walnut } k \text{ red right after move } k
詳しい解説

操作 kk を行った直後に、クルミ kk を赤く塗る。他のクルミはすべて以前の色を保つ(最初はすべて黒)。最初のステップの仮定により、操作 kk で赤くなるクルミは、その時点で常に二つの隣接が同じ色である——両方黒か、両方すでに赤か——決して片方ずつということはない。