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 を満たすことを証明せよ。
ステップ 1/5: どの操作もその番号をまたがないと仮定する
∀k: (a<b<k) or (k<a<b)\forall k:\ (a<b<k)\ \text{or}\ (k<a<b)
詳しい解説

背理法として、すべての kk について、操作 kk で交換される二つのクルミ a,ba,b が a<b<ka<b<k または k<a<bk<a<b を満たし、決して a<k<ba<k<b にならないと仮定する。