名古屋大学 1993年度理系数学第4問(b) 解答・解説

問題

$M = {1, 2, \dots\dots, n}$ を1から $n$ までの自然数の集合， $f$ を $M$ から $M$ への写像とし，

f_{1} = f, f_{2} = f \circ f_{1} = f \circ f, f_{3} = f \circ f_{2} = f \circ f \circ f, \dots\dots,

f_{k} = f \circ f_{k - 1} = f \circ f \circ \dots\dots \circ f (k 個の合成), \dots\dots

とする．次の(1)，(2)を証明せよ．

(1) $1, 2, \dots\dots, n, n + 1$ の中から異なる2つの $p$ ， $q$ を選び， $f_{p} (1) = f_{q} (1)$ とすることができる．

(2) $f_{1} (1), f_{2} (1), \dots\dots, f_{n} (1)$ がすべて互いに異なるならば， $f_{n} (1) = 1$ である．

出典：名古屋大学 1993年度前期日程第2次学力試験理系第4問(b)

方針

列 $f_{1} (1), f_{2} (1), \dots$ は常に $M$ の元を値にとる。(1)は $n + 1$ 個の値を $n$ 個の場所へ入れる鳩の巣原理である。(2)では，はじめの $n$ 個がすべて異なるなら，それらは $M$ 全体をちょうど一度ずつ含む。値1が早い位置で現れると，次の項が $f_{1} (1)$ と一致してしまうので，値1が現れる位置は最後の $n$ 番目しかない。

解答

(1)

$f$ は $M$ から $M$ への対応なので，どの自然数 $k$ についても $f_{k} (1) \in M$ である。したがって $f_{1} (1), f_{2} (1), \dots, f_{n + 1} (1)$ は， $n$ 個の元からなる集合 $M = {1, 2, \dots, n}$ の中に入る $n + 1$ 個の値である。 $n + 1$ 個の値がすべて異なることはできないから，異なる2つの番号 $p, q$ を選んで $f_{p} (1) = f_{q} (1)$ とすることができる。

(2)

$f_{1} (1), f_{2} (1), \dots, f_{n} (1)$ がすべて互いに異なるとする。これらはすべて $M$ の元であり，個数も $n$ 個であるから， $M$ の各元がちょうど一度ずつ現れる。したがって，この中のどこかに値 $1$ が現れる。

そこで $f_{j} (1) = 1$ となる番号 $j$ を考える。もし $j < n$ なら， $f_{j + 1} (1) = f (f_{j} (1)) = f (1) = f_{1} (1)$ である。ここで $1$ と $j + 1$ はどちらも $1, 2, \dots, n$ の範囲にある異なる番号である。これは $f_{1} (1), \dots, f_{n} (1)$ がすべて互いに異なることに反する。

したがって $f_{j} (1) = 1$ となる番号は $j = n$ でなければならない。よって $f_{n} (1) = 1$ である。

別解。(2)を循環の言葉で見ると， $1$ から始めて $f$ を繰り返した列は，はじめの $n$ 項で $M$ のすべての値を一度ずつ通る。もし途中で $1$ に戻れば，その直後から同じ並びが繰り返され，はじめの $n$ 項の中に同じ値が2回現れる。したがって， $1$ に戻るのは $n$ 項目でなければならない。

名古屋大学 1993年度理系数学 第4問(b)

問題

方針

解答

(1)

(2)

名古屋大学 1993年度
理系数学第4問(b)