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)\} 是芳香的。
第 3/5 步:边太少而无法覆盖所有顶点
通俗地说

三条边至多能触及六个“顶点位置”,而当边只能取间隔 2,3,42,3,4 时,要覆盖五边形状间隔图的全部五个顶点是不可能的。

at most 3 edges among 5 vertices ⇒ some vertex has degree 0\text{at most }3\text{ edges among }5\text{ vertices}\ \Rightarrow\ \text{some vertex has degree }0
详细分析

在 55 个顶点 a+1,…,a+5a+1,\dots,a+5 之间总共至多有 33 条边(间隔 22、33、44 各一条),且不允许间隔为 11 的边,直接检查这些间隔能连接哪些顶点对,可知不可能让全部 55 个顶点同时度数 ≥1\ge1:总有一个顶点被孤立。这与芳香条件(每个元素都需要一个伙伴)矛盾,因此 b≤5b\le5 是不可能的。