MathLabs

Problem 5

Find the minimum positive integer kk for which there exists a function f:Z→{1,2,…,k}f:\mathbb Z\to\{1,2,\dots,k\} such that f(x)≠f(y)f(x)\ne f(y) whenever ∣x−y∣∈{5,7,12}|x-y|\in\{5,7,12\}.
Step 1 of 5: Set up the four-color greedy construction
Previous stepNext step
f(0)=1,f(x)∈{1,2,3,4}f(0)=1,\qquad f(x)\in\{1,2,3,4\}
Detailed analysis

Assign f(0)=1f(0)=1 and then color the integers in the order 0,1,−1,2,−2,…0,1,-1,2,-2,\ldots. When a new integer xx is colored, only already colored integers at distance 5,7,5,7, or 1212 can forbid colors.