Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Let's assume $x,y>0$ (clearly, we can do this, since if what we want to prove doesn't hold, then it doesn't hold if we replace $x$ with $-x$ and/or $y$ with $-y$). Let's work with non-negative integers only. The negation of what we want to prove states that there is a set $S\subset \mathbb N$ s.t. $S,S+x,S+y,S+x+y$ are mutually disjoint, and their union is $\mathbb N$. This means that, working with formal power series, $1+t+t^2+\ldots=\left(\sum_{s\in S}t^s\right)(1+t^x)(1+t^y)$. Assume now that $y<x$. We have $\frac{1+t+t^2+\ldots}{1+t^y}=(1+t+\ldots+t^{y-1})+(t^{2y}+t^{2y+1}+\ldots+t^{3y-1})+\ldots=\mathcal E$. When we divide $\mathcal E$ by $1+t^x$ we have to get a series whose only coefficients are $0$ and $1$, and this will yield the contradiction: our series contains $1+t+\ldots+t^{y-1}$, because $y<x$. There must be a $k$ s.t. $x\in(2ky,(2k+1)y-1)$ (the interval is open because the endpoints are even, but $x$ is odd). However, there is an $\alpha\in\overline{0,y-1}$ s.t. $x+\alpha=(2k+1)y$, and this means that if our power series has no negative terms (to get rid of $t^{(2k+1)y}$, which does not appear in $\mathcal E$), when multiplied by $1+t^x$ contains $t^{(2k+1)y}$, but $\mathcal E$ doesn't have this term, so we have a contradiction.

OFFICIAL SOLUTION Suppose that there exist a colouring function $f: \mathbb{Z} \rightarrow \{R,B,G,Y\}$ with the property that for any integer $a$ \[ f\{a,a+x,a+y,a+x+y\} = \{R,B,G,Y\}. \] In particular, colouring the integer lattice by the rule \[ g: \mathbb{Z} \times \mathbb{Z} \rightarrow \{R,B,G,Y\}, g(i,j) = f(ix+jy), \] we obtain that the vertices of any unit square have all four different colours. Claim 1: If there exists a column $i \times \mathbb{Z}$ such that $g | i \times \mathbb{Z}$ is not periodical with period 2, then there exists a row $\mathbb{Z} \times j$ such that $g | \mathbb{Z} \times j$ is not periodical with period 2. Proof: If $g | i \times \mathbb{Z}$ is not periodical, then we can find the configuration $\begin{matrix} Y \\ B \\ R \end{matrix}$; using the adjacent unit squares, we get $\begin{matrix} RYR \\ GBG \\ YRY \end{matrix}$ and also $\begin{matrix} YRYRY \\ BGBGB \\ RYRYR \end{matrix}$ and so on. Thus we obtain three periodical lines. $\Box$ Claim 2: If for one integer $i,g_i = g | \mathbb{Z} \times i$ is periodical with period 2, then for every $j \in \mathbb{Z}, g_j = g | \mathbb{Z} \times j$ has period 2. The values of $g_i$ are the values $g_j$ if $i \equiv j \pmod{2}$ and the other values if $i \not \equiv j \pmod{2}$. Proof: Applying the square rule to the line $\ldots RBRBRB \ldots$ we get $\begin{matrix} \ldots YGYGY \ldots \\ \ldots RBRBR \ldots \end{matrix}$ and next $\begin{matrix} \ldots RBRBR \ldots \\ \ldots YGYGY \ldots \\ \ldots RBRBR \ldots \end{matrix}$ or $\begin{matrix} \ldots BRBRB \ldots \\ \ldots YGYGY \ldots \\ \ldots RBRBR \ldots \end{matrix}$ A similar argument holds for the rows below the line $\mathbb{Z} \times i$. $\Box$ Changing between the 'rows' and 'columns' we have similar claims. So we can suppose that the rows are periodical with period 2 and $g(0,0)= R, g(1,0)=B$. Therefore $g(y,0) = B$ ($y$ is odd). The row $\mathbb{Z} \times \{x\}$ is odd too; hence $ g(\mathbb{Z} \times \{x\}) = \{Y,G\ $. From $g(y,0) = f(xy) = g(0,x)$ we get a contradiction. Remark: The same result is true for $x = 2^k(2p+1), 2^k (2q+1)$; just take $g(i,y) = f(\frac{ix+jy}{2^k})$.

Hopefully this is different form the above: As everyone else did, note that the set $\{a, a+x, a+y, a+x+y\}$ must have 4 distinct colors. Assume $\gcd{x, y} = 1$, or just only work with multiples of the $\gcd$. Let the "colors" have values assigned to them, let's say $\{-3, -1, 1, 3\}$ for fun (it doesn't matter). Let $c_i$ be the color number assigned to the number $i$. Firstly assign color numbers to $c_0, c_1, \ldots, c_{x+y-1}$. Since $\{a, a+x, a+y, a+x+y\}$ is 4 distinct colors, the $c_i$ satisfy a recurrence: $c_{x+y+i}+c_{x+i}+c_{y+i}+c_i = -3-1+1+3 = 0$. The characteristic polynomial of this recurrence is $Z^{x+y}+Z^x+Z^y+1 = (Z^x+1)(Z^y+1)$. Since I let $\gcd(x, y) = 1$, and both are odd, the polynomial has a double root at $-1$ and single roots at roots of unity. Therefore, the characteristic polynomial is of the form $(Cn + D) \cdot (-1)^n + \sum_{\text {roots of unity } \omega_i} C_i \cdot \omega_i^n$. Since the $\omega$ terms are bounded, but the linear term isn't, the magnitude of terms can grow arbitrarily large, so they will no longer lie in the set $\{-3, -1, 1, 3\}$, contradiction. $_\blacksquare$ Edit: Blah yeah, see below. $C = 0$ is possible. Hmmm, I can't see how to patch this.

mathocean97 wrote: $(Cn + D) \cdot (-1)^n + \sum_{\text {roots of unity } \omega_i} C_i \cdot \omega_i^n$. Since the $\omega$ terms are bounded, but the linear term isn't, the magnitude of terms can grow arbitrarily large, so they will no longer lie in the set $\{-3, -1, 1, 3\}$, contradiction. $_\blacksquare$ We could have $C=0$ though, if $c_0+\cdots+c_{x+y-1}t^{x+y-1}$ is always divisible by $1+t$ no matter what we choose for the $c_i$ (for instance, if $c_0 = \cdots = c_{x+y-1}$, since $x+y-1$ is odd). --- Also, let's fix grobber's solution: grobber wrote: Let's assume $x,y>0$ (clearly, we can do this, since if what we want to prove doesn't hold, then it doesn't hold if we replace $x$ with $-x$ and/or $y$ with $-y$). Let's work with non-negative integers only. The negation of what we want to prove states that there is a set $S\subset \mathbb N$ s.t. $S,S+x,S+y,S+x+y$ are mutually disjoint, and their union is $\mathbb N$. This is not quite true, but almost true. Let $R$ be the set of red integers, so $R,R+x,R+y,R+x+y$ are pairwise disjoint (if $R+x,R+y$ intersect, then so do $R,R+x-y$, etc.), and also cover the integers (exactly one of $n,n-x,n-y,n-x-y$ is red for each integer $n$; actually this gives us pairwise disjoint-ness too). Note that we don't necessarily know that $R+x$ (for instance) is monochromatic, but it is true that such $R$'s existence would allow a construction with $R+x,R+y,R+x+y$ all blue, yellow, and green, respectively. Following this post, $R$ is purely periodic with some period $\ell>0$. If $f$ denotes the indicator function of $R$, then $f(n)+f(n-x)+f(n-y)+f(n-x-y)=1$ for $n=0,1,\ldots,\ell-1$, so \[ P(t)=\sum_{k=0}^{\ell-1}f(k)t^k\implies P(t)(1+t^x)(1+t^y)\equiv 1+t+\cdots+t^{\ell-1}\pmod{t^\ell-1}. \]Now $4P(1)=\ell$, so $\ell = 2^r s$ for some $r\ge2$ and odd $s$. If $\gcd((t^{2^r}-1)/(t^2-1),(1+t^x)(1+t^y)) = 1$ (as polynomials), then $\frac{t^{2^r}-1}{t^2-1}\mid P(t)$ (in $\mathbb{Z}[t]$), so $2^{r-1}\mid P(1) = \ell/4 = 2^{r-2} s$, contradiction. Since $1+t^{2^u}$ is irreducible for $u=1,2,\ldots,r-1$, we have some $1+t^{2^u}\mid (1+t^x)(1+t^y)$, which is absurd, since $\gcd(1+t^{2^u},1+t^z) = 1$ for any odd $z$.

I'd like to propose a solution based on a different idea- an application of discrete fourier transform (DFT). Let $f(n)$ be the indicator function of, for example, the red integers. Suppose on the contrary: \[ f(n) + f(n-x) + f(n-y) + f(n-x-y) =1 \,, \forall n\in \mathbb{Z} \]As mentioned in the above post, $f$ is periodic. We can establish that without using Skolem-Mahler-Lech theorem. Let us take some integer $T,\, T>x+y$ and consider the following $(x+y)$-tuples: $\left(f(kT+1), f(kT+2),\cdots, f(kT+x+y) \right)\,, k=0,1,\ldots$. Obviously, there are two of them, for $k=k_1$ and $k=k_2$ that coincide, which yields $f$ is periodic with period $\ell=(k_2-k_1)T$. We proceed by considering the discrete fourier transform $\hat{f}$ of $f$. \[\hat{f}(n):= \frac{1}{\ell}\sum_{k=0}^{\ell-1} f(k)\cdot e^{\frac{-2\pi i n\cdot k}{\ell}}\,\,\,\,\,\,\,\,\text{(1)} \]The inverse Fourier formula holds: \[f(n)= \sum_{k=0}^{\ell-1} \hat{f}(k)\cdot e^{\frac{2\pi i n \cdot k}{\ell}} \,\,\,\,\,\,\, \text{(2)}\] For given $f,g$ , complex valued, periodic with period $\ell$, let us define its inner product as: \[\langle f,g \rangle_{L^2} = \frac{1}{\ell}\sum_{k=0}^{\ell-1} f(k)\cdot \overline{g(k)}\]and on the Fourier side as: \[\langle f,g \rangle_{\hat{L}^2} = \sum_{k=0}^{\ell-1} f(k)\cdot \overline{g(k)}\] Then the following properties take place: \[\langle f,g\rangle_{L^2} = \langle \hat{f}, \hat{g}\rangle_{\hat{L}^2} \](Parseval identity) \[\|f\|_{L^2}= \|\hat{f}\|_{\hat{L}^2} \](Plancherel identity) In our case, since $f(\cdot),f(\cdot-x), f(\cdot-y), f(\cdot-x-y)$ are orthogonal with the same $L^2$ norm, we obtain: \[ \|f\|_{L^2}^{2}=\frac{1}{4} \,\,\,\,\,\,\, \text{(3)} \]Hence, $\hat{f}(0) = \frac{1}{\ell} \sum f(k) =\frac{1}{4}$. Furthermore, for a given $a\in \mathbb{Z}$, we have: $\widehat{f(n-a)} = \hat{f}(n)\cdot e^{-\frac{2\pi i n a}{\ell}}$. Hence: \[ \hat{f}(n) (1+\omega_n^x)(1+\omega_n^y) = \hat{1}= \delta(n) \,\,\,\,\,\,\text{(4)} \]where $\omega_n=e^{-\frac{2\pi i n}{\ell}},\, \delta(n)=1$ for $n=0$ and $\delta(n)=0$ if $ n\neq 0$ Denote: \[ A=\{n\in \mathbb{Z}\mid 0\leq n\leq \ell-1, \omega_n^x=-1 \text{ or }\omega_n^y=-1 \} \]Thus, using (4), we have $ \hat{f}(n)=0, \, n\not\in (A\cup \{0\})$. Now, applying (2), for $n=xy $ and $n=2xy$, we get: \[ f(xy) = \hat{f}(0) + \sum_{n\in A} \hat{f}(n)\cdot \omega_n^{x\cdot y} = \frac{1}{4} - \sum_{n\in A} \hat{f}(n) \]because of $\hat{f}(0)=\frac{1}{4}$ and $\omega_n^{xy} = -1$ when $n\in A$. Here we use the fact $x,y$ are both odd. In the same way: \[ f(2xy) = \frac{1}{4} + \sum_{n\in A} \hat{f}(n) \]It means that $f(xy)+f(2xy)=\frac{1}{2}$ which is imposible since $f(n)\in \{0,1\}$.

hyperbolictangent wrote: so if you look at the 4-tuple (s, s + b, s + a, s + a + b) where we assume WLOG a > b then it's easy to see this tuple must be rainbow now look at the 4-tuple (s + a, s + a + b, s + 2a, s + 2a + b) the first two coordinates of this tuple are the last two coordinates of the previous one so (s + 2a, s + 2a + b) must be colored with some permutation of the (distinct) colors assigned to (s, s + b) continuing this way, we see that (s + ab, s + ab + b) must be colored with some permutation of the (distinct) colors assigned to (s + a, s + a + b) now we do the same thing for b-shifts look at (s, s + b, s + a, s + a + b) and (s + b, s + 2b, s + a + b, s + a + 2b) again we have some overlap, which tells us (s + 2b, s + a + 2b) must be colored with some permutation of the (distinct) colors assigned to (s, s + a) once more, continuing this forces (s + ab, s + ab + a) to be colored with some permutation of the (distinct) colors assigned to (s + b, s + a + b) thus s + ab must be colored the same as s + a + b which means s + ab + a must be colored the same as s + b and s + ab + b must be colored the same as s + a and finally that s + ab + a + b must be colored the same as s Why is $s+ab$ the same as $s+a+b$ though?

dgrozev wrote: In our case, since $f(\cdot),f(\cdot-x), f(\cdot-y), f(\cdot-x-y)$ are orthogonal with the same $L^2$ norm, we obtain: \[ \|f\|_{L^2}^{2}=\frac{1}{4} \,\,\,\,\,\,\, \text{(3)} \]Hence, $\hat{f}(0) = \frac{1}{\ell} \sum f(k) =\frac{1}{4}$. Hi bro. Sorry that I can't understand how you obtain $ \|f\|_{L^2}^{2}=\frac{1}{4}$. Could you write it in detail? Thank you so much! Update: I think this part is not necessary...

Assume on the contrary that there exists a coloring such that for each integer $s$, $s$, $s+x$, $s+y$, and $s+x+y$ are all different colors. Let $C_s(a,b)$ denote the color of $s+ax+by$. Then, $C_s(a,b)$, $C_s(a,b+1)$, $C_s(a+1,b)$, and $C_s(a+1,b+1)$ are all distinct. We also know that $C_s(a+1,b)$, $C_s(a+1,b+1)$, $C_s(a+2,b)$, and $C_s(a+2,b+1)$ are all distinct. Therefore, \[\{C_s(a,b),C_s(a,b+1)\}=\{C_s(a+2,b),C_s(a+2,b+1)\}\]and similarly, \[\{C_s(a,b),C_s(a+1,b)\}=\{C_s(a,b+2),C_s(a+1,b+2)\}\]Suppose $C_s(a,b)\neq C_s(a,b+2)$ for some $a,b$. Then, $C_s(a,b)$, $C_s(a,b+1)$, $C_s(a,b+2)$ are all distinct. Since $C_s(a+1,b+1)$ cannot be any of those colors, so its color is fixed, fixing the colors of $C_s(a+1,b)$, which happens to equal $C_s(a,b+2)$ and $C_s(a+1,b+2)=C_s(a,b)$. In particular, $C_s(a+1,b)\neq C_s(a+1,b+2)$, which means that $C_s(a+1,b)$, $C_s(a+1,b+1)$, $C_s(a+1,b+2)$ are all distinct, so we can apply the same operation. Note that in this way we get that $C_s(a,b)=C_s(a+1,b+2)=C_s(a+2,b)$. Thus, colors are periodic either by $2x$ or $2y$. Let the minimum period be $k$ with $4\nmid k$, but then there is more of one color, clearly false by considering the grid globally (since each $2\times 2$ square has equal parts of each color). We are done.

Here's a completely elementary combinatorial solution. Assign the colors labels of $1, 2, 3, 4$, and let $C(x)$ be the color of $x$. We will look at an infinite table where the entry in the $a$th row and $b$th column is equal to the color of $ax+by$. In particular, any $2 \times 2$ subgrid of this table must have four distinct values. Claim. Suppose some row $a$ in this table is not periodic with period $2$. Then row $a+2$ must be identical to row $a$. Proof. Actually, I claim that we can describe the contents of row $a$ explicitly. Because no two consecutive entries in a row may be identical, there must exist three consecutive distinct entries in row $a$, say $1, 2, 3$ at positions $b-1, b, b+1$. It follows that the entry at $(a+1, b)$ is fixed (in this case, at $4$), and because no two entries in row $a+1$ can be identical that $(a, b+2)$ contains $4$. Repeating this process, it necessitates that row $a$ consists of all four colors cycled with period $4$. As row $a+1$ also contains four colors cycled with period $4$ shifted by $2$ from row $a$, it follows that rows $a$ and $a+2$ are identical. $\blacksquare$ This implies that either all the rows are periodic with modulo $2$ or all the columns are periodic with modulo $2$; assume the former. But the entry at $(a_1, b_1)$ must be identical to the entry at $(a_1-y, b_1+x)$, but this is impossible because $b_1+x$ and $b_1$ are opposite parity.

This problem was given to me by Ritwin. WLOG, say that $x$ and $y$ are both positive. FTSOC, assume that there do not exist two integers differing by one of $x$, $y$, $x+y$, or $x-y$ such that they are the same color. Then, consider any positive integer $k$. Now consider the set of numbers \[\{k,k+x,k+y,k-x,k-y,k+x+y,k-x-y,k+x-y,k-x+y\}.\]Notice that by our contradiction assumption, $k$ must be its own color (different from the other $8$). Therefore we have three colors left to color $8$ numbers, and by Pigeonhole Principle, we get that there must exist some set of $4$ numbers out of these $8$ that have the same color. I claim that the only possible set of four is then $\{k+x+y,k+x-y,k-x+y,k-x-y\}$. FTSOC, assume that $k+x$ is in the set of four. Notice then that $k+y$, $k-y$, $k+x+y$, and $k+x-y$ can then not be in the set of four. This means that the other numbers in the set of four must be $k-x$, $k-x-y$, and $k-x+y$. However, note that $k-x$ and $k-x-y$ differ by $y$, a contradiction. Therefore $k+x$ cannot be in the set of four. Symmetrically, we can conclude $k-x$, $k+y$, and $k-y$ cannot be in the set of four either. This only leaves us with four elements, so $\{k+x+y,k+x-y,k-x+y,k-x-y\}$ must be the same color. Now, since this applies to any $k$, consider $k=m+x+y$. We then get that $m$, $m+2x+2y$, $m+2x$, and $m+2y$ must be the same color. Inductively, we can conclude that for any two integers $m$ and $n$ such that $m=ax+by$ and $n=cx+dy$, $m$ and $n$ are the same color if $a\equiv b\mod 2$ and $c\equiv d \mod 2$. We can also conclude that this is an if and only if statement, as $0$, $x$, $y$, and $x+y$ must all clearly have different colors. Now consider $a=3xy$ and $b=3xy$. Notice then that $3x^2y+3xy^2$ has the same color as $x+y$, since both $3xy$ and $3xy$ are odd. However, notice that \[3x^2+3y^2=(3xy-y)x+(3xy+x)y,\]and $3xy-y$ and $3xy-x$ are both even, since $x$ and $y$ are odd. This means that $3x^2y+3xy^2$ also has the same color as $0x+0y=0$. But we already established that $0$ and $x+y$ have different colors, so this is a contradiction! Therefore there must eventually exist two integers that differ by $x$, $y$, $x+y$, or $x-y$ that have the same color.

PureRun89 wrote: dgrozev wrote: In our case, since $f(\cdot),f(\cdot-x), f(\cdot-y), f(\cdot-x-y)$ are orthogonal with the same $L^2$ norm, we obtain: \[ \|f\|_{L^2}^{2}=\frac{1}{4} \,\,\,\,\,\,\, \text{(3)} \]Hence, $\hat{f}(0) = \frac{1}{\ell} \sum f(k) =\frac{1}{4}$. Hi bro. Sorry that I can't understand how you obtain $ \|f\|_{L^2}^{2}=\frac{1}{4}$. Could you write it in detail? Thank you so much! Update: I think this part is not necessary... Because these $4$ objects are orthogonal, have the same norm, and sum up to a vector with norm $1$. A kind of Pythagorean theorem. Some years ago, I wrote a note about this method with an application on some Olympiad problems, including this one.