MathLabs

第4题

如果一个正整数集合至少包含两个元素，且其中每个元素都与其他至少一个元素有公共素因数，就称这个集合是芳香的。设 P(n)=n2+n+1P(n)=n^2+n+1。求最小的正整数 bb，使得存在非负整数 aa，使集合 {P(a+1),P(a+2),…,P(a+b)}\{P(a+1),P(a+2),\dots,P(a+b)\} 是芳香的。
第 2/5 步：可能的边太少的图
上一步下一步
通俗地说

把 bb 个连续值之间可能共享的因子建模为一张图；上一步表明只有三种特定的“间隔”边是可能的，且每种至多一条。

b≤5 ⇒ at most one edge of gap 2, 3, 4, and none of gap 1b\le5\ \Rightarrow\ \text{at most one edge of gap }2,\,3,\,4,\text{ and none of gap }1
详细分析

对于间隔 22，被 77 整除要求两个指标是 2,4(mod7)2,4\pmod7 这两个根；在五个连续指标中至多出现一对。对于间隔 33，被 33 整除要求两个指标都为 1(mod3)1\pmod3，在五个连续指标中也至多一对。对于间隔 44，被 1919 整除要求根为 7,11(mod19)7,11\pmod{19}，同样至多一对。间隔 11 不可能，因为最大公约数为 11。因此五个连续指标之间至多有三条共享因子边，每种间隔一条，不可能覆盖全部五个顶点。