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)。
第 1/5 步：建立四色贪心染色
上一步下一步
f(0)=1,f(x)∈{1,2,3,4}f(0)=1,\qquad f(x)\in\{1,2,3,4\}
详细分析

令 f(0)=1f(0)=1，然后按 0,1,−1,2,−2,…0,1,-1,2,-2,\ldots 的顺序给整数染色。给新整数 xx 染色时，只有与它距离为 5,7,5,7, 且已经染色的整数会禁用颜色。 1212