2018年 日本数学オリンピック本選 第３問 解答例
$${S = \{1, 2, \cdots , 999\} }$$とおく。$${f}$$は$${S}$$上で定義され$${S}$$に値をとる関数であり、任意の$${S}$$の要素$${n}$$に対して
$${f^{n+f(n)+1}(n) = f^{nf(n)}(n) = n}$$
が成り立つとする。このとき、$${f(a)=a}$$をみたす$${S}$$の要素$${a}$$が存在することを示せ。
ただし$${f^k(n)}$$で$${\underbrace{f(f(\cdots f}_{k\text{個}} (n)\cdots ))}$$を表すものとする。
考え方：
$${f}$$が全単射であることは明らかです。
$${n}$$をスタートとして$${f}$$を次々作用させていくと、
$${n\rightarrow f(n) \rightarrow f^2(n) \rightarrow \cdots \rightarrow n \rightarrow f(n) \rightarrow \cdots}$$
と、ある周期をもって繰り返すことがわかります。
この周期について深堀りしていきましょう。
条件式から$${n+f(n)+1}$$も$${nf(n)}$$も
この周期の倍数であることがわかります。
更に何が言えるでしょうか。
実験として、例えば$${n=2}$$としてみましょう。
周期を$${T}$$とします。
$${f(2)+3}$$と$${2f(2)}$$の両方が$${T}$$の倍数です。
よって、$${2(f(2) + 3) - 2f(2) = 6}$$も$${T}$$の倍数です。
なので$${T}$$としてあり得るのは$${1, 2, 3, 6}$$となります。
$${T=1}$$のときは$${f(2)=2}$$、
$${T=2}$$のときは例えば$${f(2)=3}$$とすれば矛盾はありません。
$${T=3}$$となることはあるでしょうか。
$${f(2) + 3}$$が$${3}$$の倍数なので、$${f(2)=3a}$$とおけます。
次に、$${3a + f(3a) +1}$$が3の倍数となるので、
$${f^2(2) = f(3a) = 3b -1}$$となります。
さらに$${3b - 1 + f(3b - 1) +1}$$が3の倍数となるので、
$${f^3(2) = f(3b-1)}$$が$${3}$$の倍数になりますが、
これは$${f^3(2) = 2}$$に反します。
よって$${T\neq 3}$$となることがわかります。
この考え方を他の$${n}$$も適用して、
周期が$${1}$$でなければ偶数になることが示せそうです。
$${S}$$の要素数が奇数なので、周期がすべて偶数になることはあり得ません。
よって、周期が$${1}$$となる要素が存在することが示せます。
解答例：
条件より$${f}$$は全単射である。
各$${S}$$の要素$${n}$$に対して$${f^{l}(n)=n}$$となる最小の正の整数$${l}$$を$${T_n}$$とする。
$${f^{T_n + k}(n) = f^k(f^{T_n}(n)) = f^k(n)}$$
であるから、$${T_n = T_{f(n)} = \cdots = T_{f^{T_n - 1}(n)}}$$である。
また、$${f}$$の作用でうつり合う要素を１つの集合とすることで、
$${S}$$は要素数$${T_n}$$の部分集合に重複なく分解できる。
さて、$${f^k(n) = n}$$となる整数$${k}$$が$${T_n}$$の倍数ではないとすると、
整数$${r}$$および$${0\leqq s < T_n}$$である整数$${s}$$を用いて
$${k = rT_n + s}$$と一意に表すことができる。
このとき、
$$
f^k(n) = f^{rT_n + s}(n) = f^s(n) = n
$$
となり、$${T_n}$$が最小であることに反する。
よって、$${k}$$は$${T_n}$$の倍数である。
条件より$${n+f(n)+1}$$と$${nf(n)}$$はいずれも$${T_n}$$の倍数である。
$${T_n ( = T_{f(n)}= \cdots= T_{f^{T_n - 1}(n)})}$$が$${3}$$以上の奇数であり、
その素因数の１つを$${p}$$とすると、
$${0 \leqq k \leqq p-1}$$なる整数$${k}$$に対して
$${f^k(n)+f^{k+1}(n)+1}$$と$${f^k(n)f^{k+1}(n)}$$はいずれも$${p}$$の倍数となる。
このとき、$${f^k(n)}$$と$${f^{k+1}(n)}$$の一方は$${p}$$の倍数であり、
もう一方は$${p}$$で割ると$${p-1}$$余る値であることが必要となるが、
このとき
$$
\begin{align*}
f(n) \equiv f^3(n) \equiv \cdots \equiv f^{T_n}(n) = n (\text{mod } p)
\end{align*}
$$
となり矛盾する。
よって、$${T_n}$$は$${1}$$か偶数となる。
$${S}$$の要素数は奇数であるため、
複数の部分集合に重複なく分割したとき、
要素数が奇数の部分集合が必ず存在する。
つまり、$${f(a)=a}$$となる要素$${a}$$が存在する。
お知らせ：
少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)