第3题

设

\mathbb{N}

表示正整数集合。若一个函数

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

对任意正整数

a

和

b

，都有

f(a)

整除

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

，则称该函数为 bonza 函数。求最小的实常数

c

，使得对于所有 bonza 函数

f

以及所有正整数

n

，均有

f(n)\le cn

。

第 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$ 。