Does there exist a bijection $f:\mathbb{N}^{+} \rightarrow \mathbb{N}^{+}$, such that there exist a positive integer $k$, and it's possible to have each positive integer colored by one of $k$ chosen colors, such that for any $x \neq y$ , $f(x)+y$ and $f(y)+x$ are not the same color?
Problem
Source: 2019 China TST Test 3 P3
Tags: Coloring, bijection, combinatorics
25.03.2019 12:45
Yes, such a bijection exists, and it allows us to color $\mathbb{N}^+$ in two colors complying to the condition. Setting $u=f(x)+y; v=x+f(y)$ , one can see that it's equivalent to require $x+y$ and $f(x)+f^{-1}(y)$ to be of different colors, providing $y\neq f(x)$. The idea is to define consecutively $f$ starting from $f(1)$ and in the same time to color appropriately one by one the natural numbers. Let $f(1):=2; f(3):=1$. It imposes that the color of $f(1)+f^{-1}(1)=2+3=5$ is different from the color of $1+1=2$. So far, this is the only condition, we must comply to. So, we color $2$ in white and $5$ in black. We say $f$ is not fully defined at point $x\in\mathbb{N}^+$ if we haven't yet defined $f(x)$ or $f^{-1}(x)$. Till now, the only point $f$ is fully defined at is $x=1$. Now, we consecutively apply the following: Extension step. Let $n$ be the first natural $f$ is not fully defined at. It means either $f(n)$ or $f^{-1}(n)$ or both are not defined. Consider first the case $f(n)$ doesn't exists. Let $D$ be the subset of naturals where $f^{-1}$ is defined. We should ensure that $f(n)+f^{-1}(x)$ and $n+x$ are of different colors for any $x\in D$. Denote $D':=\{n+x : x\in D\}$. If there exists $y\in D'$ which is not yet colored, we color it arbitrary. Then choose $N$ big enough such that the minimal element of the set $\{N+f^{-1}(x):x\in D \} $ is bigger than the maximal colored natural number. Then we define $f(n):=N$ and for any $x\in D$ we color $f(n)+f^{-1}(x)$ in the color opposite to the color of $n+x$. The case when $f^{-1}(n)$ is not defined is similar with appropriate changes - we should ensure $f^{-1}(n)+f(x)$ is of different color compared to $n+x$. In the case both $f(n), f^{-1}(n)$ are not yet defined, we first define $f(n)$ as above and then apply again the same step to define $f^{-1}(n)$ Applying consecutively that extension step, we define $f$ over $\mathbb{N}^+$ and it is bijection. If there is still not colored naturals, we can color them arbitrary
30.03.2019 21:11
This problem is provided by me
31.05.2020 14:14
Can someone send a official or more beautiful solution (in english) of this problem, please.