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 2 of 5: Bound the number of forbidden colors

Previous step Next step

\#\{y:|x-y|\in\{5,7,12\},\ |y|<|x|\}\le 3

Detailed analysis

For a positive $x$ , the previously colored neighbors can only be $x-5,x-7,x-12$ when they lie in the earlier part of the order; for a negative $x$ the symmetric statement holds. Thus at most three previously colored neighbors exist, and at most three colors are forbidden.