第5問
リス Bushy と Jumpy は冬に備えて 個のクルミを集めた。Jumpy はクルミに から まで番号をつけ、お気に入りの木の周りに円形に 個の小さな穴を掘った。翌朝、Jumpy は Bushy が各穴にクルミを一つずつ入れたものの、番号を気にしていなかったことに気づいた。不満に思った Jumpy は、 回の操作からなる手順でクルミを並べ替えることにした。 回目の操作では、Jumpy はクルミ に隣接する二つのクルミの位置を入れ替える。ある が存在して、 回目の操作で入れ替えるクルミ と が を満たすことを証明せよ。
ざっくり言うと
ちょうど二つの黒いクルミからなるブロックは決して壊れない。なぜなら、どちらか一方を赤くするには、外側の隣接ともう一方が同じ色でなければならないが、そうなっていないからである。
詳しい解説
ステップ2により、クルミは両方の隣接がすでに同じ色である場合にのみ赤くなり得る。したがって長さがちょうど の黒いブロックは決して一つを失うことがない。なぜならその二つのクルミはそれぞれ黒い相棒一つと赤い外側隣接一つを持ち——色が一致しないからである。長さが偶数 の黒いブロックでは、内部のクルミが（必ず両隣が黒い状態で）赤くなると、長さ と の二つの部分ブロックに分裂し、 は奇数なので一方は偶数、他方は奇数になる。