MathLabs

第3题

设 N\mathbb{N} 表示正整数集合。若一个函数 f:N→Nf:\mathbb{N}\to\mathbb{N} 对任意正整数 aa 和 bb,都有 f(a)f(a) 整除 ba−f(b)f(a)b^a-f(b)^{f(a)},则称该函数为 bonza 函数。求最小的实常数 cc,使得对于所有 bonza 函数 ff 以及所有正整数 nn,均有 f(n)≤cnf(n)\le cn。
第 6/7 步:恰好取到 c = 4 的构造
f(n)={1n odd16n=42n even, n≠4 is bonza and has f(4)=16=4⋅4f(n)=\begin{cases}1 & n\text{ odd}\\16 & n=4\\2 & n\text{ even},\,n\ne4\end{cases}\ \text{is bonza and has}\ f(4)=16=4\cdot4
详细分析

取奇数 nn 时 f(n)=1f(n)=1,f(4)=16f(4)=16,n≠4n\ne4 的偶数时 f(n)=2f(n)=2。此函数是 bonza 的:若 aa 为奇数,f(a)=1f(a)=1 整除一切;若 a=4a=4,利用奇数 bb 满足 b4≡1(mod16)b^4\equiv1\pmod{16}、b≠4b\ne4 的偶数满足 16∣b416\mid b^4 且 16∣21616\mid2^{16},以及 b=4b=4 直接验证,可得 16∣b4−f(b)1616\mid b^4-f(b)^{16};若 aa 为偶数且 a≠4a\ne4,按 bb 在各情形下的奇偶性可验证 2∣ba−f(b)22\mid b^a-f(b)^2。因为 f(4)=16=4⋅4f(4)=16=4\cdot4,此函数说明界 f(n)≤4nf(n)\le4n 不能再改进,故 c=4c=4 是最优的。