ISL 2023 N8

204

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

問題

$f : Z_{> 0} \to Z_{> 0}$
$f^{b f (a)} (a + 1) = (a + 1) f (b) \forall a, b \in Z_{> 0}$
を満たす関数を全て求めよ。

考え軽くをまとめながら解答書いていきます。
$P (a, b)$ で与式の代入を表すことにする。
まず解は $f (n) = n + 1$ だけ...？
単射は言えそう。 $f (x) = f (y)$ として
$P (a, x), P (a, y)$ から $f^{x f (a)} (a + 1) = f^{y f (a)} (a + 1)$ が分かって $x \neq y$ なら周期的になる事が分かる。しかしそれが $f$ の値域が無限集合であることに矛盾するみたいな感じ。 $a = 1$ と固定しても証明できそう。以下厳密に証明する。

補題1

単射である。

$f (1) = c$ とする。
$S = {f^{c} (2), f^{2 c} (2), f^{3 c} (2), \dots}$ と定める。 $P (a, b)$ で $a$ を動かすことで $f$ の値域は無限集合であり $P (1, b)$ で $f^{b c} (2) = 2 f (b)$ であるから $b$ を動かすことで $S$ は無限集合となる。
$f (x) = f (y), x - y = k > 0$ となる正の整数 $x, y$ が存在したと仮定して矛盾を導く。
$P (1, x), P (1, y)$ より $f^{(y + k) c} (2) = f^{x c} (2) = f^{y c} (2)$ である。また非負整数 $n$ において $f^{(y + k + n) c} (2) = f^{(y + n) c} (2)$ が成り立つ。この等式を繰り返し用いることで任意の $b ≧ y$ において $f^{b c} (2)$ は $f^{y c} (2), f^{(y + 1) c} (2), \dots, f^{(y + k - 1) c} (2)$ のいずれかと値が同じであるから $S$ が無限集合であることと矛盾する。よって補題は示せた。

単射であることを上手く使いたい。
$P (f (a) - 1, b)$ とすれば右辺が $a, b$ 対称になるから $a$ と $b$ 入れ替えれば良さそうだ。しかしその前に $f (a) = 1$ となるような $a$ の存在を否定しないといけない。
$f (n) = 1$ としたら $P (1, n)$ で $f^{n c} (2) = 2$ となって周期的となって矛盾しそう。というか $f^{2 n c} (2) = f^{n c} (2) = 2$ で $f (2 n) = 1$ となって単射性に矛盾しそう。

補題2

$f (n) = 1$ となるような $n \in Z_{> 0}$ は存在しない。

$P (1, n)$ より $f^{n c} (2) = 2$ であるから
$f^{2 n c} (2) = f^{n c} (2) = 2$ であるが $P (1, 2 n)$ から $2 = f^{2 n c} (2) = 2 f (2 n)$
$\Rightarrow f (2 n) = 1 = f (n)$ これは単射性に矛盾する。

$P (f (a) - 1, b), P (f (b) - 1, a)$ から
$f^{b f (f (a) - 1) + 1} (a) = f (a) f (b) = f^{a f (f (b) - 1) + 1} (b) \dots (i)$
これは強力な等式であるが $b f (f (a) - 1)$ と $a f (f (b) - 1)$ の大小関係に注意しなければならない。
$b = 1$ としたら補題2を使っていい感じになりそう。

補題3

$f$ の値域は $2$ 以上の全ての整数である。

$(i)$ に $b = 1$ を代入し単射性から $f (f (a) - 1) - a f (f (1) - 1) > 0 \Rightarrow f^{f (f (a) - 1) - a f (f (1) - 1)} (a) = 1$ $f (f (a) - 1) - a f (f (1) - 1) < 0 \Rightarrow f^{a f (f (1) - 1) - f (f (a) - 1)} (1) = a$
$f (f (a) - 1) - a f (f (1) - 1) = 0 \Rightarrow a = 1$
1番上のときは補題2より矛盾であるので $a \neq 1$ で $f^{a f (f (1) - 1) - f (f (a) - 1)} (1) = a$ を得る。 $a$ は任意に取れるので $f$ の値域は $2$ 以上の全ての整数である。

$(i)$ に $b = f (a)$ 、より一般的に $b = f^{k} (a)$ を代入したらいい感じに。
$f^{f^{k} (a) f (f (a) - 1) + 1} (a) = f^{a f (f^{k + 1} (a) - 1) + 1 + k} (a)$
$f^{x} (a) = f^{y} (a) \Rightarrow x = y$ を示せばさらに議論が進みそう。これは周期性からすぐ示せる。

補題4

$f^{x} (a) = f^{y} (a) \Rightarrow x = y$

$f^{x} (a) = f^{y} (a), x > y$ と仮定して矛盾を示す。単射性から
$f^{x - y} (a) = a \Rightarrow f^{n (x - y)} (a) = a$
$a = 1$ なら補題2から矛盾だから $a > 1$ とする。 $P (a - 1, x - y)$ から $a = f^{(x - y) f (a - 1)} (a) = a f (x - y)$
$\Rightarrow f (x - y) = 1$ 補題2から矛盾。

先ほどの式から
$f^{k} (a) f (f (a) - 1) = a f (f^{k + 1} (a) - 1) + k$
$f (f (a) - 1), f (f^{k + 1} (a) - 1)$ が入ってて扱いにくそうだが法 $a$ の剰余で考えるととても扱いやすそうな式。 $P (a - 1, b)$ で
$f^{b f (a - 1)} (a) = a f (b)$ となって相性良さそう。 $f^{k} (a)$ が $a$ の倍数となるような $k$ についての補題を以下示す。

補題5

$f^{k} (a)$ が $a$ の倍数 $\Leftrightarrow k$ が $a$ の倍数

$f^{k} (a) f (f (a) - 1) = a f (f^{k + 1} (a) - 1) + k$ において $k = 1$ から $a$ と $f (f (a) - 1)$ は互いに素であるから補題の主張はすぐに分かる。

$P (a - 1, b)$ を使って以下の補題を示す。

補題6

$f (a - 1)$ は $a$ の倍数。

$P (a - 1, b)$ から
$f^{b f (a - 1)} (a) = a f (b)$ で $f^{b f (a - 1)} (a)$ は $a$ の倍数。補題5より
$b f (a - 1)$ は $a$ の倍数、 $b$ は $a$ と互いに素となるように取れば $f (a - 1)$ は $a$ の倍数となる。

補題6から特に $f (a) ≧ a + 1$ が分かる。
これと補題3と単射から任意の $n$ で $f (n) = n + 1$ になることが証明できそうだ。補題3から $2, 3, \dots, k$ の値を $f$ は取るが $n ≧ k$ で $f (n) > k$ だから ${2, 3, \dots, k} = {f (1), f (2), \dots, f (k - 1)}$ となる。特に両辺の要素数は同じだから $f (1), f (2), \dots, f (k - 1)$ は $2, 3, \dots, k$ の並び替えである。これを $k$ と $k + 1$ で比べることで $f (k) = k + 1$ が分かりそう。

$f (n) = n + 1 \forall n \in Z_{> 0}$ である。

補題3より $f (t) = 2$ となる $t$ が存在するが補題6から $f (a) ≧ a + 1$ であるから $2 = f (t) ≧ t + 1$ より $t = 1$ 。以下帰納法で示す。 $f (n) = n + 1$ が $n ≦ k - 1$ で成り立つと仮定する。補題3より $f (t) = k + 1$ となる $t$ が存在する。 $k + 1 = f (t) ≧ t + 1 \Rightarrow k ≧ t, k > t$ と仮定すると帰納法の仮定より $t + 1 = f (t) = k + 1$ となり矛盾。よって $t = k, f (k) = k + 1$ となる。帰納法より $f (n) = n + 1 \forall n \in Z_{> 0}$ となる。
十分性はすぐに分かる。