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 4 of 5: Force equality two steps apart under a three-color assumption

Previous step Next step

f(x-5),f(x),f(x+7)\text{ are pairwise distinct},\qquad f(x+2)=f(x)

Detailed analysis

Assume a three-coloring exists. The three integers $x-5,x+7,x+2$ have pairwise distances $12,5,5$ ; use instead the source's first triple $x-5,x,x+7$ : their pairwise distances are $5,7,12$ , so their colors are all distinct. The point $x+2$ is at distance $7$ from $x-5$ and $5$ from $x+7$ , so it cannot use either of those two colors and must have $f(x+2)=f(x)$ .