Is it possible to partition the set of integers into three disjoint sets so that for every positive integer $n$ the numbers $n$, $n-50$ and $n+1987$ belong to different sets?
Problem
Source: Bulgaria EGMO TST 2016 Day 2 Problem 1
Tags: partition, number theory, combinatorics
13.10.2023 21:13
Will be edited
17.11.2023 01:02
@above you firstly say that any two integers with difference $1937$ must be in the same group but immediately afterwards state that $y$ and $y+1937$ are in different groups, how does this happen??
16.05.2024 11:30
Ok, I think this works. Suppose it is possible and for brevity denote $a=50$ and $b=1987$. The problem condition insists on any two numbers with difference $a$, $b$ or $a+b$ to be of different colour. Hence for all $n$ we have that each of $n+a$, $n+b$ and $n+a+b$ is in a different colour from that of $n$. Since the colours are three, it follows that $n+a$, $n+b$ and $n+a+b$ are in the same colour - but the difference of $n+a+b$ with the other two is either $a$ or $b$, therefore necessarily the numbers $n+a$ and $n+b$ are in the same colour. We obtained that any two numbers with difference $b-a$ are in the same colour. In particular, $n+a+b$ and $n+2a$ have the same colour. But since $n$, $n+a$ and $n+a+b$ have different colours, if follows that $n$, $n+a$, $n+2a$ have different colours. The same must hold for $n+a$, $n+2a$, $n+3a$, therefore for all $n$ the numbers $n$ and $n+3a$ have the same colour, i.e. any two numbers with difference $3a$ are in the same colour. Finally, note that $3a$ and $b-a$ are relatively prime, as $\gcd(150, 1937) = \gcd(150, 150 \cdot 13 - 1937) = \gcd(150, 13) = 1$, hence the equation $1 = 3aX + (b-a)Y$ has an integral solution by Bezout's lemma, implying that any two numbers with difference $1$ are in the same colour. But then all integers are in the same colour, contradiction.