第三题（45分）

设f→是严格递增函数，满足f（1）=1且对任意正整数n，有f（f（n））=f（n）+n。求f（n）的表达式。

江辰扫了一眼。

“函数方程题，经典题型。”

他几乎没思考，直接写：

“解：先求前几项。由f（1）=1，代入n=1得f（f（1））=f（1）+1，即f（1）=1+1=2，矛盾？因为f（1）=1，所以f（f（1））=f（1）=1，右边f（1）+1=2，1=2矛盾？”

江辰愣住了。

“题目出错了？”

他重新读题：“f→是严格递增函数，满足f（1）=1且对任意正整数n，有f（f（n））=f（n）+n。”

代入n=1：f（f（1））=f（1）+1→f（1）=1+1=2，但f（1）=1，矛盾。

“这……”

江辰皱眉。

三秒后，他明白了。

“哦，f（1）=1，但f（f（1））=f（1）吗？不，f（1）=1，所以f（f（1））=f（1）=1，右边应该是1+1=2，確实矛盾。”

“除非……题目中的是正整数，但可能包含0？或者f（1）=1是初始条件，但函数方程对n≥2成立？”

他继续往下想。

“先假设题目没错，那么矛盾说明我的推理有问题。f（f（n））=f（n）+n，当n=1时，f（f（1））=f（1）+1=2，所以f（f（1））=2。”

“而f（1）=1，所以f（1）=1，那么f（f（1））=f（1）=1，但需要等於2，所以必须f（1）≠1？可题目明確说了f（1）=1。”

江辰感觉脑子有点乱。

“这题……有问题？”

他决定先跳过，看第四题。

第四题（45分）

设p是奇素数，a，a，…，a_p是整数。证明：存在整数k（1≤k≤p）使得∑_i=1^p（a_i+k-a_i）2能被p2整除，这里下標模p理解（即a_p+1=a_1等）。

江辰看完，眼睛一亮。

“数论组合题，有点意思。”

“∑（a_i+k-a_i）2=∑a_i+k2-2∑a_i+ka_i+∑a_i2=2∑a_i2-2∑a_i+ka_i，因为∑a_i+k2=∑a_i2。”

“所以要证存在k使2∑a_i2-2∑a_i+ka_i≡0dp2，即∑a_i2≡∑a_i+ka_idp22？不对，模p2。”

“即证存在k使∑a_i+ka_i≡∑a_i2dp2。”

“记s_k=∑a_ia_i+k，要证存在k使s_k≡s_0dp2，其中s_0=∑a_i2。”

“这等价於证存在k使s_k-s_0≡0dp2。”

“考虑所有k的s_k之和？或者用多项式方法……”

江辰脑子飞速转动。

十秒后，他有了思路。

“用傅立叶变换（离散傅立叶变换）。”

“设a（x）=∑a_ix^i（多项式），则s_k是a（x）a（x^-1）中x^k项的係数？不对，循环卷积。”

“实际上，s_k=∑a_ia_i+k是序列a_i的自相关函数。”

“要证存在k使s_k≡s_0dp2。如果所有s_k≡s_0dp2都不成立，那么所有s_k-s_0≡0dp2都不成立……”

“用反证法：假设对所有k都有s_ks_0dp2，则s_k-s_0≡r_kdp2，其中r_k是1到p2-1之间的数。”

“考虑∑_k=1^p（s_k-s_0）=∑_k∑_ia_i（a_i+k-a_i）=……”

江辰在草稿纸上快速计算。

两分钟后，他找到了关键等式。

“有了！∑_k=1^ps_k=p∑a_i2，所以∑_k=1^p（s_k-s_0）=p∑a_i2-p∑a_i2=0。”

“但如果每个s_k-s_0都不被p2整除，它们的和模p2不可能为0，矛盾。”

“但如果每个s_k-s_0都不被p2整除，它们的和模p2不可能为0，矛盾。”

“所以存在k使p2整除s_k-s_0。”

“严谨化：设b_i=a_idp，考虑模p下的序列b_i，用类似论证可得存在k使∑b_ib_i+k≡∑b_i2dp，然后提升到模p2……”

四分钟，第四题搞定。

江辰看了眼时间：950。

第四题做完，还剩第三题。

他回过头看第三题。

“函数方程f（f（n））=f（n）+n，f严格递增，f（1）=1。”

“代入n=1得f（1）=2，矛盾。所以要么题目错了，要么我的理解错了。”

江辰想了想，突然灵光一闪。

“等等，f是→，通常指正整数，但有时也包含0。如果包含0，那么f（0）可能存在。”

“设f（0）=c，则f（f（0））=f（c）=f（0）+0=c，所以f（c）=c。”

“由f严格递增，f（0）=c，f（1）=1，如果c＜1，则f（0）＜f（1），但0＜1，可以。c必须是整数，所以c=0。”

“那么f（0）=0，f（1）=1，代入n=1：f（f（1））=f（1）+1=2，所以f（1）=2？但f（1）=1，矛盾。”

“还是矛盾。”

江辰皱眉。

“除非……f（1）不是1？但题目明確说了f（1）=1。”

他决定换个思路。

“假设f（1）=1，那么f（f（1））=f（1）=1，但方程要求f（f（1））=f（1）+1=2，矛盾。”

“所以题目一定有印刷错误？或者是自然数集包括0，且f（0）=1？”

“设f（0）=1，那么f（1）是多少？由严格递增，f（1）＞f（0）=1。”

“代入n=0：f（f（0））=f（1）=f（0）+0=1，所以f（1）=1，但f（1）＞1，矛盾。”

“也不行。”

江辰感觉这题像个死胡同。

他看了眼时间，952。

“算了，先按標准方法解，假设f（1）=1成立，忽略n=1的矛盾。”

“令g（n）=f（n）-n，则方程变为f（f（n））=f（n）+n→f（n+g（n））=n+g（n）+g（n）=n+2g（n）。”

“但f（n+g（n））又等於f（f（n））=f（n）+n=n+2g（n），自洽。”

“由严格递增，g（n）非负且递增？不一定。”

“尝试求前几项：设f（1）=1，则f（f（1））=f（1）=1，但方程要求等於2，所以矛盾。跳过n=1。”

“从n=2开始：f（f（2））=f（2）+2，设f（2）=a，则f（a）=a+2。”

“由严格递增，f（1）=1＜f（2）=a，所以a≥2。”

“f（3）=b，则f（b）=b+3，且b＞a≥2。”

“继续推导……”

江辰在草稿纸上列出一串等式。

两分钟后，他猜出了答案。

“f（n）=φn+ψ，其中φ是黄金比例（1+√5）2？不对，必须是整数函数。”

“实际上，经典解是f（n）=φn或类似形式，但需要验证。”

他快速验证了一下。

“设φ=（1+√5）2≈1。618，则φ2=φ+1。”

“如果f（n）=φn，则f（f（n））=φφn≈φ2n=φn+n=f（n）+n，近似成立。”

“但严格成立需要数论性质，这是经典的beatty序列。”

江辰决定直接写答案：

“解：f（n）=φn，其中φ=（1+√5）2，且n≥1时成立。验证：由beatty定理，φφn=φ2n=（φ+1）n=φn+n=φn+n=f（n）+n，当φn不是整数时成立，而φ是无理数，φn永不为整数，故等式成立。”