トップ› 名古屋大学› 1973年› 理系第2問

名古屋大学 1973年理系第2問解説

方針・初手

与えられた関数の定義域と値域がともに $1$ 以上 $n$ 以下の整数であることに着目する。これにより、両端の値について $f(1) \geqq 1$ および $f(n) \leqq n$ が必ず成り立つ。関数の単調非減少性（$k_1 < k_2$ ならば $f(k_1) \leqq f(k_2)$）を利用し、$f(k) \geqq k$ となる最大の整数 $k$ を考えることで証明を進める。背理法で条件が切り替わる境界を探すアプローチと、集合の最大元に着目する直接的なアプローチがある。

解法1

$f(k) = k$ となる整数 $k$ ($1 \leqq k \leqq n$) が存在しないと仮定し、背理法で示す。

仮定より、すべての $k$ ($1 \leqq k \leqq n$) に対して $f(k) > k$ または $f(k) < k$ のいずれかが成り立つ。関数 $f$ の値域は $1 \leqq r \leqq n$ であるから、$f(1) \geqq 1$ および $f(n) \leqq n$ である。仮定より $f(1) \neq 1$ であるから $f(1) > 1$ となる。同様に $f(n) \neq n$ であるから $f(n) < n$ となる。

したがって、$1 \leqq k \leqq n$ の範囲で $f(k) > k$ を満たす $k$ は少なくとも $1$ つ存在する。そのような $k$ の中で最大のものを $p$ とする。 $f(n) < n$ であるから $p \neq n$ であり、$p < n$ となる。よって、$p+1$ は $1 \leqq p+1 \leqq n$ を満たす整数である。

$p$ は $f(k) > k$ を満たす最大の整数であるから、$f(p+1) > p+1$ は成り立たない。背理法の仮定より $f(p+1) \neq p+1$ であるから、

$$ f(p+1) < p+1 $$

となる。 $f(p)$ および $f(p+1)$ は整数であるから、これまでの不等式は次のように言い換えられる。 $f(p) > p$ より

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

$f(p+1) < p+1$ より

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

一方、問題の条件より $p < p+1$ ならばつねに $f(p) \leqq f(p+1)$ である。これらを組み合わせると、

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

すなわち $p+1 \leqq p$ となるが、これは不合理である。したがって、最初の仮定は誤りであり、$f(m)=m$ となる整数 $m$ が存在することが示された。

解法2

集合 $A$ を次のように定める。

$$ A = \{ k \mid 1 \leqq k \leqq n, f(k) \geqq k \} $$

関数 $f$ の値域より $1 \leqq f(1)$ がつねに成り立つため、$1 \in A$ であり、$A$ は空集合ではない。また、$A$ は有限集合 $\{1, 2, \dots, n\}$ の部分集合であるから、最大の要素をもつ。集合 $A$ の最大の要素を $m$ とする。

$m \in A$ であるから、定義より

$$ f(m) \geqq m $$

が成り立つ。ここで、$f(m) > m$ であると仮定し、矛盾を導く。

$l = f(m)$ とおくと、仮定より $l > m$ である。 $m \leqq n$ であり、関数 $f$ の値域より $f(m) \leqq n$ であるから、$l \leqq n$ となる。したがって、$l$ は $1 \leqq m < l \leqq n$ を満たす整数である。

問題の単調非減少性の条件より、$m < l$ ならばつねに $f(m) \leqq f(l)$ である。 $l = f(m)$ であるから、これを代入して

$$ l \leqq f(l) $$

となる。これは $l$ が集合 $A$ の条件を満たす、すなわち $l \in A$ であることを意味する。しかし、$l > m$ であり、これは $m$ が集合 $A$ の最大の要素であることに矛盾する。

したがって、$f(m) > m$ となることはなく、初めに示した $f(m) \geqq m$ と合わせて

$$ f(m) = m $$

でなければならない。以上より、$f(m) = m$ となる整数 $m$ が存在することが示された。

解説

本問は、連続関数における「中間値の定理」や「ブラウワーの不動点定理」の離散版（整数版）と言えるテーマである。関数 $g(k) = f(k) - k$ とおくと、問題の条件から $g(1) \geqq 0$ かつ $g(n) \leqq 0$ となり、$k$ が増加する過程で $g(k)$ の値がどこかで正から負に切り替わることが直感的に予想できる。解法1ではこの「切り替わる瞬間」を捉えるために背理法を用い、解法2では「条件を満たす最大の元」を定義して直接的に証明した。定義域と値域が有限の整数に制限されていることと、関数の単調性をうまく組み合わせる論証の典型的な手法であり、同様の考え方は整数問題や論理問題で広く応用できる。