名古屋大学 1993年度 前期日程 第2次学力試験 場合の数・論証・証明理系数学 第4問(b)

(1) 任意の自然数$k$について$$f_k(1)\in M$$である。$f_1(1),f_2(1),\dots ,f_{n+1}(1)$は$n$個の元しかない$M$に入る$n+1$個の値なので、鳩の巣原理により少なくとも2つは等しい。したがって異なる$$p,q\in \{1,2,\dots ,n+1\}$$を選んで$f_p(1)=f_q(1)$とできる。

(2) $f_1(1),\dots ,f_n(1)$がすべて異なるなら、これら$n$個の値は$M$の全要素をちょうど一度ずつ取る。ゆえに、ある$j\in \{1,\dots ,n\}$について$$f_j(1)=1$$である。

もし$j<n$なら$$f_{j+1}(1)=f(f_j(1))=f(1)=f_1(1)\mathrm{.}$$ここで$1$と$j+1$はともに$1,\dots ,n$に属する異なる添字なので、最初の$n$項が互いに異なるという仮定に反する。したがって$j=n$であり、$$f_n(1)=1$$である。

写像$f$を各頂点から矢印が1本出る有向グラフとして見る。1から矢印をたどる軌道は有限なので必ず循環へ入り、最初の$n$項がすべて異なる場合には1を含む長さ$n$の循環でなければならない。

集合$M$の各元を頂点とし、各$x\in M$から$f(x)$へ矢印を引く。このとき$$1⟶f_1(1)⟶f_2(1)⟶\cdots$$は頂点1から矢印をたどる道である。

(1) $n+1$回たどって得る$f_1(1),\dots ,f_{n+1}(1)$は$n$頂点上の値だから、同じ頂点を少なくとも2回通る。これが所要の$p,q$を与える。

(2) 最初の$n$項がすべて異なるなら、その道は$M$の全$n$頂点をちょうど一度ずつ通る。特に頂点1へ戻るが、$n$項目より前に戻れば、その直後から軌道が最初と同じ順序で繰り返され、最初の$n$項内に重複が生じる。したがって戻る時刻は$n$に限られ、$$f_n(1)=1$$となる。