MathLabs

第2题

对多项式 PP 与正整数 nn,定义 PnP_n 为满足 a<b≤na<b\le n 且 ∣P(a)∣−∣P(b)∣|P(a)|-|P(b)| 能被 nn 整除的正整数对 (a,b)(a,b) 的个数。求所有整系数多项式 PP,使得对一切正整数 nn 都有 Pn≤2021P_n\le2021。
第 2/6 步:关键引理:前 n 个值模 n 两两不同
Lemma: P(1),P(2),…,P(n) pairwise distinct(modn)\text{Lemma: } P(1),P(2),\ldots,P(n)\ \text{pairwise distinct}\pmod n
详细分析

将多项式 P 换为其相反数不改变计数,故可假设 P 在充分大的正自变量处为正。若前 n 个值中有两个模 n 同余,取 A 使得自变量 an+y 与 an+z 在 a 不小于 A 时对应的值为正,再取 k 大于 2A 加 2021。所得 2(k−A) 个值只落在模 kn 时的 k 个余数类中,而这些余数类模 n 都给出同一余数。计算这些类中的碰撞,至少有 k−2A 个、因而超过 2021 个数对模 kn 同余。对应的正自变量互不相同且小于 kn,与上界矛盾。因此前 n 个值模 n 两两不同。