MathLabs

第5题

求最小正整数 kk，使得存在函数 f:Z→{1,2,…,k}f:\mathbb Z\to\{1,2,\dots,k\}，满足当 ∣x−y∣∈{5,7,12}|x-y|\in\{5,7,12\} 时总有 f(x)≠f(y)f(x)\ne f(y)。
第 5/5 步：与距离十二的条件矛盾
上一步下一步
f(x)=f(x+2)=⋯=f(x+12),∣(x+12)−x∣=12f(x)=f(x+2)=\cdots=f(x+12),\qquad |(x+12)-x|=12
详细分析

反复使用 f(x+2)=f(x)f(x+2)=f(x)，得到从 xx 到 x+12x+12 的六次递推中颜色相同。但两者距离为 1212，定义条件要求 f(x)≠f(x+12)f(x)\ne f(x+12)。所以三色不可能，k≥4k\ge4；结合构造得 k=4k=4。