第3問

\mathbb{N}

を正の整数全体の集合とする。すべての正の整数

a

および

b

に対して

f(a)

が

b^a-f(b)^{f(a)}

を割り切るとき、関数

f:\mathbb{N}\to\mathbb{N}

は bonza であるという。すべての bonza 関数

f

およびすべての正の整数

n

に対して

f(n)\le cn

が成り立つような、最小の実数定数

c

を求めよ。

ステップ 1/7: 対角代入 a = b = n

前のステップ次のステップ

f(n)\mid n^n\quad\text{for all }n

詳しい解説

$P(a,b)$ を主張 $f(a)\mid b^a-f(b)^{f(a)}$ とする。 $P(n,n)$ をとると $f(n)\mid n^n-f(n)^{f(n)}$ を得る。 $f(n)^{f(n)}$ 自身が $f(n)$ の倍数である( $f(n)\ge1$ のため)ので、それを足し戻すと $f(n)\mid n^n$ が分かる。