問題一覧へ戻る
k を正の整数とする. 整数に対して定義され整数値をとる単射 f について, |i−j|≦k なる任意の整数の組 (i,j) に対して |f(i)−f(j)|≦k が成り立つ. このとき, 任意の整数の組 (i,j) に対し |f(i)−f(j)|=|i−j| が成り立つことを示せ.
平山：差が 1 のところ見たら終わりでは？？ 兒玉：単射やん草 宿田：単射wwwwww 渡辺：本質すぎる 平山：単射じゃなければ、そもそも成立せず… 渡辺：ひでえ
k に関する帰納法により示す. k=1 のとき単射性より明らかに成立する. 以下ある k−1≧1 で成立したと仮定し, k の場合を示す.
集合 Si={f(i),f(i+1),⋯,f(i+k−1)} について考える. 単射性より Si は k 個の相異なる整数からなるが, 条件より最小の元と最大の元の差は k 以下であるから, Si は連続する k 個の整数からなる. 同様に Si−1 も連続する k 個の整数からなることに留意する.
ここで集合 Si′={f(i),⋯,f(i+k−2)} が連続する k−1 個の整数でないと仮定し, Si−Si′ の唯一の元を X とおく. このとき Si−1 が連続する k 個の整数たり得るためには f(i−1)=X が必要であるが, これは単射性に反する.
すなわち, 以上より k−1 の場合に帰着されたことがわかる. よって示された.