Problem 5

Find the minimum positive integer

k

for which there exists a function

f:\mathbb Z\to\{1,2,\dots,k\}

such that

f(x)\ne f(y)

whenever

|x-y|\in\{5,7,12\}

Step 5 of 5: Contradict the distance-twelve condition

Previous step Next step

f(x)=f(x+2)=\cdots=f(x+12),\qquad |(x+12)-x|=12

Detailed analysis

Iterating $f(x+2)=f(x)$ gives equality along the six increments from $x$ to $x+12$ . But the defining condition requires $f(x)\ne f(x+12)$ because their distance is $12$ . Thus three colors are impossible, so $k\ge4$ ; together with the construction, $k=4$ .