名古屋大学 1993年 理系 第5問 解説

方針・初手

(1) は、写像によって作られる数列 $f_k(1)$ の値がとり得る範囲と、考える項数に注目する。いわゆる「鳩の巣原理（部屋割り論法）」の典型的な適用である。

(2) は、仮定から数列の最初の $n$ 項が集合 $M$ のすべての要素を網羅していることに着目する。集合 $M$ の要素である $1$ もこの $n$ 項のいずれかとして現れるはずであり、それを $f$ で写した結果を考えることで矛盾を導く。

解法1

(1)

写像 $f$ は $M$ から $M$ への写像であるから、任意の自然数 $k$ に対して $f_k(1) \in M$ である。

集合 $M = \{1, 2, \dots, n\}$ の要素数は $n$ 個である。 一方、$f_1(1), f_2(1), \dots, f_{n+1}(1)$ は全部で $n+1$ 個の値である。

これら $n+1$ 個の値はすべて $M$ に属するため、鳩の巣原理（部屋割り論法）により、少なくとも2つの値は等しくなる。

したがって、$1, 2, \dots, n, n+1$ の中から異なる2つの $p, q$ を選び、$f_p(1) = f_q(1)$ とすることができる。（証明終）

(2)

仮定より、$f_1(1), f_2(1), \dots, f_n(1)$ はすべて互いに異なる。 また、これらはすべて集合 $M = \{1, 2, \dots, n\}$ の要素である。

要素数がともに $n$ であり、すべて異なる値をとることから、集合として次が成り立つ。

$$\{f_1(1), f_2(1), \dots, f_n(1)\} = M$$

$1 \in M$ であるから、$1$ は $\{f_1(1), f_2(1), \dots, f_n(1)\}$ のいずれかの要素と等しい。 すなわち、ある自然数 $k$ ($1 \le k \le n$) が存在して、

$$1 = f_k(1)$$

と表せる。この両辺を写像 $f$ で写すと、

$$f(1) = f(f_k(1))$$

となる。

ここで、写像の定義より $f(1) = f_1(1)$ であるから、

$$f_1(1) = f(f_k(1))$$

となる。

(i) $1 \le k \le n-1$ のとき

定義より $f(f_k(1)) = f_{k+1}(1)$ であるから、

$$f_1(1) = f_{k+1}(1)$$

となる。 しかし、仮定より $f_1(1), f_2(1), \dots, f_n(1)$ はすべて互いに異なるので、等号が成り立つためには $1 = k+1$ でなければならない。 これを解くと $k = 0$ となるが、これは $1 \le k$ に矛盾する。 したがって、$1 \le k \le n-1$ の範囲には $1 = f_k(1)$ を満たす $k$ は存在しない。

(ii) $k = n$ のとき

(i) の結果から、必ず $k = n$ でなければならない。 よって、

$$1 = f_n(1)$$

である。（証明終）

解説

写像の反復に関する論証問題である。

(1) は有限集合からの写像を繰り返し適用したときに、必ずどこかで「ループ」に入ることを示す基本的な証明であり、鳩の巣原理の応用として頻出の考え方である。

(2) は、仮定の「すべて異なる」という条件を「集合が一致する（全単射である）」と言い換えることが最大のポイントである。$f_k(1)$ という文字の添え字の動きと、それらを $f$ で写したときの動きを連動させて考えることで、$f_n(1) = 1$ を導くことができる。関数の定義域と値域の対応関係を正確に把握する力が問われている。

答え

(1) 鳩の巣原理（部屋割り論法）により、$n+1$ 個の値 $f_1(1), \dots, f_{n+1}(1)$ が $n$ 個の要素からなる集合 $M$ に属することから示された。

(2) 仮定から $\{f_1(1), \dots, f_n(1)\} = M$ となることを用い、$1 = f_k(1)$ ($1 \le k \le n$) とおいて両辺を $f$ で写すことで、$k \le n-1$ の場合に矛盾が生じることから示された。