正の整数全体からなる集合をNとする。関数 $f: N \rightarrow N$ が「エモい」とは、任意の正の整数 $a, b$ に対して、$f(a)$ が $b^a - f(b)^{f(a)}$ を割り切ることである。任意のエモい関数 $f$ と、任意の正の整数 $n$ に対して、$f(n) \leq cn$ が成り立つような実数 $c$ としてありうる最小の値を求めよ。

1. 問題の内容

正の整数全体からなる集合をNとする。関数 $f: N \rightarrow N$ が「エモい」とは、任意の正の整数 $a, b$ に対して、$f(a)$ が $b^a - f(b)^{f(a)}$ を割り切ることである。任意のエモい関数 $f$ と、任意の正の整数 $n$ に対して、$f(n) \leq cn$ が成り立つような実数 $c$ としてありうる最小の値を求めよ。

2. 解き方の手順

まず、$a=1$ を与えられた条件に代入すると、$f(1)$ が $b - f(b)^{f(1)}$ を割り切る。

特に、$b=f(1)$ のとき、$f(1)$ が $f(1) - f(f(1))^{f(1)}$ を割り切る。

すると、$f(1)$ は $f(f(1))^{f(1)}$ を割り切る必要がある。

$f(1)=1$ とすると、$f(a) \mid b^a - f(b)$ となる。

$a=1$ を代入すると、$f(1) \mid b - f(b)$ となる。

$f(1) = 1$ のとき、$1 \mid b - f(b)$ より $b - f(b)$ は任意の $b$ で整数である。

ここで、$f(n) = n$ とすると、$f(a) = a$ であり、$a$ が $b^a - b^a = 0$ を割り切るので $f(n) = n$ はエモい関数である。

このとき、$f(n) \leq cn$ より、$n \leq cn$ となるので、$c \geq 1$。

$f(n) = 1$ とすると、$f(a) = 1$ であり、$1 \mid b^a - 1$ なのでこれはエモい関数である。

このとき、$f(n) \leq cn$ より、$1 \leq cn$ となるので、$c \geq \frac{1}{n}$ となり、$n \rightarrow \infty$ のとき $c \rightarrow 0$ となるが、$c$ は定数なので成り立たない。

$a=2$ とする。$f(2) \mid b^2 - f(b)^{f(2)}$ となる。

$f(b) = b$ のとき、$f(2) = 2$ で、$2 \mid b^2 - b^2 = 0$ となり、$f(n) = n$ はエモい関数。

このとき、$n \leq cn$ より、$c \geq 1$。

次に、$f(1) = 2$ のとき、$2 \mid b - f(b)^2$ となる。

$b=1$ とすると、$2 \mid 1 - f(1)^2 = 1-4 = -3$ より成り立たない。

$f(n) = n^2$ とすると、$f(a) = a^2$ であり、$a^2 \mid b^a - (b^2)^{a^2}$ が成り立つ必要がある。

ここで、$a=1$ とすると、$1 \mid b - f(b)$ より、$f(b) = b$ なら成り立つ。

もし、$f(n) = k$ とすると、$f(a) = k \mid b^a - k^k$ となる。

$a=1$ とすると、$k \mid b - k^k$ となる。

$b=k^k$ とすると、$k \mid k^k - k^k = 0$ となる。

$f(n) \leq cn$ より、$k \leq cn$ となるので、$c \geq \frac{k}{n}$ となる。

$n=1$ とすると、$c \geq k$ となる。

もし $f(x) = x$ なら、$f(a) = a$ で、$a \mid b^a - f(b)^a = b^a - b^a = 0$ となる。

すると、$f(n) = n \leq cn$ より、$c \geq 1$。

$c=1$ のとき、これは条件を満たす。

3. 最終的な答え

1