2

Show that there does not exist a function $f:\mathbb{Z}\to \{1,2,3\}$ satisfying $f(x)\neq f(y)$ for all $x,y\in \mathbb{Z}$ such that $|x-y|\in \{2,3,5\}$.

Proof: Suppose by contradiction that such function exists and denote it by $f(x)$. Let $f(0)=a, f(2)=b, f(5)=c$ and then $a\neq b, a\neq c, b\neq c$ and also $a,b,c\in \{1,2,3\}$ and WLOG we put that $a=1, b=2, c=3$.

Consider $f(3)$ and since $f(3)\neq 1, f(3)\neq 3$ then $f(3)=2$.

Similarly, considering $f(7)$ and since $f(7)\neq 2, f(7)\neq 3$ then $f(7)=1$.

Also $f(8)\neq f(3)=2, f(8)\neq f(5)=3$ then $f(8)=1$.

Also $f(6)\neq f(3)=2, f(6)\neq f(8)=1$ and hence $f(6)=3$.

Finally, examining $f(4)$ we see that $f(4)\neq f(2)=2$ and $f(4)\neq f(6)=3$ and so $f(4)=1$. But $f(4)\neq f(7)=1$ and here is a contradiction.

Is it suitable proof?

RFZ
  • 16,814
  • Everything correct as far as I can see. Only thing is : the WLOG in your proof is not immediately evident to me. But i suppose it must be correct, maybe you can expand on that.. – Rutger Moody Mar 10 '17 at 08:29
  • @RutgerMoody: If you compose $f$ with a permutation of ${1,2,3}$, the given condition is still satisfied. – Taladris Mar 10 '17 at 08:32
  • @Taladris I suppose it must be true. But it is a proof by contradiction. The function with $ a=1, b=2, c=3 $ is not the same function as with $ a=1, b=3, c=2$ – Rutger Moody Mar 10 '17 at 08:50
  • If you just continue using $a,b,c$ there is no need for the WLOG problem. – Arthur Mar 10 '17 at 09:09
  • @Arthur, is this comment dedicated to me? – RFZ Mar 10 '17 at 09:47
  • 1
    Partly to you, partly to Rutger. It's just a suggestion to resolve the issue raised in this comment section. – Arthur Mar 10 '17 at 09:49
  • @Arthur you're right of course. I didn't see that – Rutger Moody Mar 10 '17 at 10:11
  • 1
    @RutgerMoody: yes, but because permutations are bijections and preserve the given condition, then the existence of one function ($a=1,b=2,c=3$) is equivalent to the existence of the other one ($a=1,b=3,c=2$). Another way to see it is that you don't actually use the fact that the codomain is ${1,2,3}$ but only that its cardinal is $3$. I agree that writing the details of the WLOG would be, as often, quite long and Arthur's suggestion is certainly the best option. – Taladris Mar 10 '17 at 11:06

0 Answers0