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 3 of 5: Complete the four-coloring

Previous step Next step

f(x)\ne f(y)\quad\text{whenever }|x-y|\in\{5,7,12\}

Detailed analysis

Choose the least available color at every stage. The preceding bound guarantees that the set of available colors is nonempty. Any forbidden pair is considered when the later endpoint is colored, so the resulting function satisfies $f(x)\ne f(y)$ whenever $|x-y|\in\{5,7,12\}$ . Hence $k\le4$ .