トップ› 名古屋大学› 1973年› 文系第5問

名古屋大学 1973年文系第5問解説

方針・初手

与えられた関数 $f(k)$ は、定義域 $\{1, 2, \dots, n\}$ から値域 $\{1, 2, \dots, n\}$ への単調非減少な関数である。証明すべきは、この関数のグラフが直線 $r = k$ と交点を持つこと、すなわち $f(m) = m$ となる不動点が存在することである。

離散的な整数値をとる関数であるため、$f(k) - k$ という値の変化に注目する。定義域の両端である $k=1$ と $k=n$ における値の範囲を考え、$f(k) > k$ を満たす最大の $k$ に着目して直接 $m$ を見つける方法（解法1）と、定義域の要素数 $n$ に関する数学的帰納法を用いて定義域を縮小していく方法（解法2）が考えられる。

解法1

関数 $f(k)$ が $f(m)=m$ を満たすような整数 $m$ ($1 \leqq m \leqq n$) が存在しないと仮定して矛盾を導く背理法、あるいは条件を満たす $k$ の集合の最大値に着目して直接証明を行うことができる。ここでは直接 $m$ の存在を示す。

$f(k) > k$ を満たす整数 $k$ ($1 \leqq k \leqq n$) の集合を $S$ とする。

(i) 集合 $S$ が空集合の場合すべての $1 \leqq k \leqq n$ に対して $f(k) \leqq k$ が成り立つ。 $k=1$ のとき、$f(1) \leqq 1$ となるが、問題の条件から $f(1)$ の値域は $1 \leqq f(1) \leqq n$ であるため、$f(1) \geqq 1$ でなければならない。したがって、$f(1) = 1$ となり、$m = 1$ とすれば $f(m) = m$ が成り立つ。

(ii) 集合 $S$ が空集合でない場合 $S$ は有限集合であるから、必ず最大の要素が存在する。その最大の要素を $l$ とおく。 $l$ は $S$ の要素であるから、定義より次が成り立つ。

$$ f(l) > l $$

ここで、$f(l)$ と $l$ はともに整数であるため、上の不等式は次のように言い換えられる。

$$ f(l) \geqq l + 1 $$

一方、$k=n$ のときを考えると、値域の条件から $f(n) \leqq n$ であるため、$f(n) > n$ となることはなく、$n$ は集合 $S$ に含まれない。したがって、集合 $S$ の最大要素 $l$ は $l < n$ を満たす。 $l$ の定義より、$l+1$ は集合 $S$ に含まれないため、次が成り立つ。

$$ f(l + 1) \leqq l + 1 $$

さらに、問題の条件である単調非減少性（$k_1 < k_2$ ならば $f(k_1) \leqq f(k_2)$）を用いると、$l < l + 1$ であるから、次が成り立つ。

$$ f(l) \leqq f(l + 1) $$

以上で得られた3つの不等式をつなぎ合わせると、次のようになる。

$$ l + 1 \leqq f(l) \leqq f(l + 1) \leqq l + 1 $$

この不等式の両端が $l+1$ で一致しているため、等号がすべて成立しなければならない。特に、$f(l + 1) = l + 1$ が導かれる。 $l < n$ より $1 < l+1 \leqq n$ であるから、$m = l + 1$ とすれば $f(m) = m$ が成り立つ。

(i), (ii) のいずれの場合においても $f(m) = m$ となる整数 $m$ が存在することが示された。

解法2

定まった正の整数 $n$ についての命題であるが、任意の正の整数 $n$ について成り立つことを数学的帰納法を用いて証明する。

(I) $n = 1$ のとき関数の定義域および値域は $\{1\}$ のみである。したがって、$f(1) = 1$ と定まるため、$m = 1$ として題意の整数 $m$ が存在する。

(II) $n = j$ ($j$ は正の整数) のとき、題意が成り立つと仮定する。すなわち、「定義域と値域が $\{1, 2, \dots, j\}$ であり、単調非減少である任意の関数は、$f(m)=m$ となる $m$ をもつ」と仮定する。

$n = j + 1$ のときを考える。関数 $f$ は $\{1, 2, \dots, j+1\}$ から $\{1, 2, \dots, j+1\}$ への単調非減少関数である。ここで、$f(j + 1)$ の値によって場合分けを行う。

(ア) $f(j + 1) = j + 1$ の場合 $m = j + 1$ とすれば $f(m) = m$ となり、条件を満たす整数 $m$ が存在する。

(イ) $f(j + 1) \neq j + 1$ の場合値域の条件から $1 \leqq f(j + 1) \leqq j+1$ であるため、$f(j + 1) \leqq j$ となる。関数 $f$ の単調非減少性より、任意の $k \in \{1, 2, \dots, j\}$ に対して次が成り立つ。

$$ 1 \leqq f(k) \leqq f(j + 1) \leqq j $$

これより、$k$ が $1$ から $j$ の範囲にあるとき、$f(k)$ の値も $1$ から $j$ の範囲に収まることがわかる。したがって、関数 $f$ の定義域を $\{1, 2, \dots, j\}$ に制限して得られる関数は、$\{1, 2, \dots, j\}$ から $\{1, 2, \dots, j\}$ への単調非減少関数となる。帰納法の仮定により、この制限された関数において $f(m) = m$ となる整数 $m$ ($1 \leqq m \leqq j$) が存在する。この $m$ は元の関数 $f$ に対しても $f(m) = m$ を満たす。

(ア), (イ) のいずれの場合も、$n = j + 1$ のとき題意を満たす整数 $m$ が存在することが示された。

(I), (II) より、すべての正の整数 $n$ に対して題意は成り立つ。

解説

本問は、連続関数における「中間値の定理」の離散版、あるいは離散数学における「不動点定理」と呼ばれるテーマを背景に持つ良問である。

関数 $y = f(x)$ のグラフを考えたとき、定義域の左端 $x=1$ ではグラフは直線 $y=x$ 上かそれより上にあり、右端 $x=n$ では直線 $y=x$ 上かそれより下にある。グラフは単調に右上がりに進むため、直感を信じれば「どこかで必ず $y=x$ を横切る（あるいは乗る）」ことは明白に思える。しかし、それを整数の離散的な性質のみを用いて厳密に証明する論理力が問われている。

解法1は、「$y=x$ より上にある最後の点」に着目するエレガントな手法である。最大値（または最小値）の存在という有限集合の性質を利用して、不等式の連鎖から等式を絞り出している。解法2は、条件の強い端の要素を取り除き、問題を小さなサイズに帰着させることで数学的帰納法を適用する堅実なアプローチである。帰納法を用いることで、考えるべき状態が絞られ論理の飛躍を防ぎやすくなる。