No function $f:\mathbb{Z}\rightarrow \{1, 2, 3\}$ satisfying $f(x)\ne f(y)$ for all integers $x,y$ and $|x-y|\in\{2, 3, 5\}$

Question

Show there does not exist a function $f:\mathbb{Z}\rightarrow \{1, 2, 3\}$ satisfying $f(x)\ne f(y)$ for all integers $x,y$ and $|x-y|\in\{2, 3, 5\}$.

This is taken from "Putnam and Beyond" and I cannot seem to understand why this cannot be true. I let $x$ be fixed and assigned $f(x)=1$, then assumed $f(y)=2, |x-y|=2.$ Then I proceeded to substitute $y-1$ and $y-3$ but did not get anywhere in finding a contradiction.

I am looking for comments about my approach and an explanation of the solution.

Answer 1

WLOG you can assign $f(0) = 1$

$f(2) \ne 1, f(2) \ne f(5)\\ f(3) \ne 1, f(3) \ne f(5)\\ f(2) = f(3)$

Again it makes thing easier to follow if you assign $f(2) = 2, f(3) = 2, f(5) = 3$.

Now, what does that imply for other numbers?

$f(7) \ne f(2), f(7) \ne f(5) \implies f(7) = f(0) = 1\\ f(8) \ne f(3), f(8) \ne f(5) \implies f(8) = f(0) = 1$

$f(4) \ne f(2), f(4)\ne f(7), f(4) = f(5) = 3\\ f(6) \ne f(3), f(6)\ne f(8), f(6) = f(5) = 3$

But then $f(4) = f(6)$ which is a contradiction.

Answer 2

Suppose such an $f$ exists. Let $A = f^{- 1}(1)$, $B = f^{- 1}(2)$, $C = f^{- 1}(3)$ partition $\mathbb{Z}$.

WLOG, assume $0 \in A$, $2 \in B$, $5 \in C$. The rest is below. (Should be hidden.)

! $2, 5 \implies 7 \in A$.
$2, 7 \implies 4 \in C$.
$0, 5 \implies 3 \in B$.
$3, 4 \implies 1, 6 \in A$, contradiction.

Answer 3

In order to show that there is no such function, we start to construct one, and see that we get into trouble. We start start with setting $f(0)=a$. Then we must have $f(2),f(3)$ and $f(5)$ all different from $a$. Furthermore, $f(2)$ and $f(5)$ must be different from one another, say $f(2)=b$ and $f(5)=c$, where now $a,b,c$ are the numbers $1,2,3$ in some order. This also forces $f(3)=b$.

We continue, and get $f(7)=a$, which lets us set $f(4)=c$. This gives $f(1)=a$. Finally, we get into trouble trying to find a value for $f(6)$, since $f(1)=a, f(3)=b$ and $f(4)=c$. Therefore there can be no such $f$.

Answer 4

This can be seen as asking to assign one of three colors to each element of $\mathbb{Z}$, so that any two numbers at distance 2 from each other receive different colors, any two numbers at distance 3 from each other receive different colors, and any two numbers at distance 5 from each other receive different colors.

However, fix any integer $n$ and consider the set $\{n, n+2, n+3, n+5\}$. Any two numbers in this set are at distance 2, 3, or 5, except for the pair $(n+2,n+3)$. Therefore, in any valid coloring, $n+2$ and $n+3$ must receive the same color.

Now, apply this for $n=0$: 2 and 3 must receive the same color. Apply this again for $n=1$: 3 and 4 must receive the same color. But this implies that 2 and 4 must receive the same color, which is not allowed. We conclude that a coloring with the specified properties does not exist.

Answer 5

take a couple of numbers and draw their graph, this makes everything simpler, we just have to check if it can be colored:

The following gif shows the thought process involved: