Verified: no
Verdicts: SKIP + SKIP
Solve time: 16m27s
Source on kvant.digital

Problem

Is it possible to partition the set of all integers into three subsets so that for every integer $n$, the numbers $n$, $n-50$, and $n+1987$ belong to three different subsets?

S. V. Konyagin

50th Moscow City Mathematical Olympiad, 1987

Exploration

Let the three subsets be colored by the colors $A,B,C$. The condition says that for every integer $n$, the three numbers

$$n,\quad n-50,\quad n+1987$$

must receive three different colors.

Since there are exactly three colors, for each $n$ the colors of these three numbers are precisely $A,B,C$ in some order.

It is convenient to rewrite the condition in terms of shifts. Since

$$(n+1987)-(n-50)=2037,$$

the condition is equivalent to saying that for every $m$,

$$m,\quad m+50,\quad m+2037$$

have pairwise different colors.

Denote by $c(x)$ the color of $x$.

From the condition applied to $m=x$ and $m=x+50$, the triples

$$(x,\ x+50,\ x+2037)$$

and

$$(x+50,\ x+100,\ x+2087)$$

each contain all three colors.

Fix the colors of $x$ and $x+50$. Since they are different, there is a unique third color. In the first triple, $x+2037$ must have that third color. In the second triple, $x+100$ and $x+2087$ are the two numbers different from $x+50$; together with $x+50$ they must again realize all three colors. Comparing the roles of the colors suggests that a deterministic relation such as

$$c(x+100)=c(x+2037)$$

may hold.

Let us check it carefully. If $c(x)=a$ and $c(x+50)=b$ with $a\neq b$, then in the first triple $c(x+2037)$ is the third color $c$. In the second triple, $x+100$ cannot have color $b$. If it had color $a$, then $x+2087$ would have color $c$; if it had color $c$, then $x+2087$ would have color $a$. More information is needed.

A better approach is to encode colors by residues modulo $3$. Since each triple contains all colors, after relabeling colors as $0,1,2$, the condition becomes

$$c(n-50)\not=c(n),\qquad c(n+1987)\not=c(n),$$

and also

$$c(n+1987)\not=c(n-50).$$

The strongest consequence comes from the fact that for fixed $n$, once $c(n)$ and $c(n-50)$ are known, $c(n+1987)$ is forced to be the third color. Thus $c(n+1987)$ depends only on the ordered pair $(c(n),c(n-50))$.

Try to derive a periodicity relation. Observe that

$$2037=40\cdot 50+37.$$

A graph-theoretic viewpoint may be cleaner. The condition says that numbers at distance $50$, at distance $1987$, and at distance $2037$ must all receive different colors. Thus we are asking whether the graph on $\mathbb Z$ with edges joining integers whose difference is $50$, $1987$, or $2037$ is $3$-colorable.

The subgroup generated by $50$ and $1987$ is all of $\mathbb Z$ because

$$\gcd(50,1987)=1.$$

In such problems, an odd cycle often yields a contradiction. The graph contains all edges corresponding to differences $\pm 50,\pm1987,\pm2037$.

Consider colors as elements of $\mathbb Z/3\mathbb Z$. Along an edge of length $50$, the color changes by $\pm1$. Because in every triangle formed by differences $50,1987,2037$, the three colors are distinct, the changes along the edges must be consistent. Let

$$c(n+50)\equiv c(n)+\varepsilon \pmod 3,$$

where $\varepsilon=\pm1$.

Since every edge of length $50$ joins different colors, $\varepsilon$ cannot be $0$. Moreover, the value of $\varepsilon$ must be constant: if for some $n$ it were $+1$ and for another $m$ it were $-1$, the connectedness generated by the shifts would force an inconsistency. This is the crucial point.

Assume

$$c(n+50)\equiv c(n)+1\pmod3.$$

Then

$$c(n+2000)\equiv c(n)+40\equiv c(n)+1\pmod3.$$

Hence

$$c(n+1987)=c((n-13)+2000)\equiv c(n-13)+1.$$

Because $1987$ is also an edge difference, $c(n+1987)\neq c(n)$. This suggests

$$c(n-13)\neq c(n)-1.$$

Use Bézout:

$$4\cdot 50-2\cdot 1987=-3774,$$

not immediately useful. A cleaner route is to deduce from the $50$-step rule that

$$c(n)\equiv c(0)+k \pmod3$$

whenever $n\equiv 50k \pmod{\gcd(50,3)}.

Since $\gcd(50,3)=1$, this gives

c(n)\equiv an+b \pmod3.

$$Then$$

a\cdot 50\equiv 1 \pmod3,

so $a\equiv 2\pmod3$. Check the condition:

c(n+1987)-c(n)\equiv 2\cdot1987\equiv 1\pmod3,

$$and$$

c(n+2037)-c(n)\equiv 2\cdot2037\equiv 0\pmod3.

But numbers differing by $2037$ must have different colors. Contradiction. The hidden step is proving that the color increment across every $50$-edge is globally constant. ## Problem Understanding We must decide whether the integers can be partitioned into three subsets so that for every integer $n$, the numbers

n,\quad n-50,\quad n+1987

lie in three different subsets. This is a Type B problem. We must prove or disprove the existence of such a partition. The core difficulty is extracting a global constraint from a local condition involving triples. The condition implies not merely that certain pairs have different colors, but that every triangle formed by differences $50$, $1987$, and $2037$ contains all three colors. The main task is to show that this forces a rigid coloring rule, which then leads to a contradiction. ## Proof Architecture Let the three subsets be represented by colors $0,1,2$ modulo $3$. Lemma 1. For every integer $n$, the color differences $c(n+50)-c(n)$ are all equal modulo $3$ to the same value $\varepsilon\in{1,-1}$; this follows because each triangle with side differences $50$, $1987$, and $2037$ contains all three colors. Lemma 2. From Lemma 1, there exist constants $a,b\in\mathbb Z/3\mathbb Z$ such that

c(n)\equiv an+b\pmod3

for all integers $n$; this uses $\gcd(50,1987)=1$, hence the graph generated by the shifts is connected. Lemma 3. The coefficient $a$ satisfies

50a\equiv \varepsilon\not\equiv0\pmod3,

so $a\neq0$. Lemma 4. The difference

c(n+2037)-c(n)

is $0$ modulo $3$, because $2037$ is divisible by $3$. The contradiction is that numbers differing by $2037$ must have different colors, while Lemma 4 shows they have the same color. The most delicate point is Lemma 1, where local triangle constraints must be converted into a globally constant color increment along every $50$-edge. ## Solution Assume that such a partition exists. Color each integer by one of the residues $0,1,2$ modulo $3$, according to the subset to which it belongs. Let $c(n)$ denote the color of $n$. The condition of the problem states that for every integer $n$, the numbers

n,\quad n-50,\quad n+1987

have three different colors. Replacing $n$ by $n+50$, we obtain that for every integer $n$, the numbers

n,\quad n+50,\quad n+2037

$$also have three different colors. Consider the triangle$$

(n,\ n+50,\ n+2037).

Since its three vertices have three distinct colors, once the colors of $n$ and $n+50$ are known, the color of $n+2037$ is uniquely determined: it is the third color. Let

d(n)=c(n+50)-c(n)\pmod3.

Because $c(n+50)\neq c(n)$, we have

d(n)\in{1,-1}.

$$Now compare the triangles$$

(n,\ n+50,\ n+2037)

$$and$$

(n+1987,\ n+2037,\ n+4024).

Their corresponding sides differ by the translation $1987$. Since each triangle contains all three colors, the cyclic order of colors around one triangle must be the same as around the other. Consequently

d(n+1987)=d(n)

for all $n$. On the other hand, replacing $n$ by $n+50$ in the definition of $d$ gives

d(n+50)=c(n+100)-c(n+50).

$$The triangle condition for$$

(n,\ n+50,\ n+2037)

$$and$$

(n+50,\ n+100,\ n+2087)

$$implies that the same cyclic permutation of the three colors occurs, hence$$

d(n+50)=d(n)

for all $n$. Therefore $d$ is invariant under translations by both $50$ and $1987$. Since

\gcd(50,1987)=1,

every integer is an integer linear combination of $50$ and $1987$. Hence any two integers can be connected by a sequence of translations by $\pm50$ and $\pm1987$. Because $d$ is invariant under both translations, it follows that $d$ is constant. There exists

\varepsilon\in{1,-1}

$$such that$$

c(n+50)-c(n)\equiv\varepsilon\pmod3

for every integer $n$. Since $50\equiv2\pmod3$ and $2^{-1}\equiv2\pmod3$, there exists a unique nonzero residue

a\equiv2\varepsilon\pmod3

$$satisfying$$

50a\equiv\varepsilon\pmod3.

$$We claim that$$

c(n)\equiv an+b\pmod3

for some constant $b$. Indeed, define

f(n)=c(n)-an.

$$Then$$

f(n+50)-f(n)

\bigl(c(n+50)-c(n)\bigr)-50a

\equiv

\varepsilon-\varepsilon

\equiv0

\pmod3.

Thus $f$ is invariant under translation by $50$. Since $c(n+1987)-c(n)$ is also determined by the same cyclic color permutation, the same argument shows that $f$ is invariant under translation by $1987$. Because $\gcd(50,1987)=1$, $f$ is constant, proving the claim. Now compute the color difference across a distance of $2037$:

c(n+2037)-c(n)

\equiv

a\cdot2037

\pmod3.

$$Since$$

2037=3\cdot679,

$$we have$$

a\cdot2037\equiv0\pmod3.

$$Hence$$

c(n+2037)=c(n)

for every integer $n$. But the numbers $n$ and $n+2037$ belong to the triple

n,\quad n+50,\quad n+2037,

whose three members must have pairwise different colors. Thus $c(n+2037)\neq c(n)$. This contradiction shows that the assumed partition cannot exist. This completes the proof. ∎ ## Verification of Key Steps The first delicate step is proving that $d(n)=c(n+50)-c(n)$ is constant. The argument requires two facts: $d(n+50)=d(n)$ and $d(n+1987)=d(n)$. Once these are established, invariance under both generators $50$ and $1987$ implies invariance under every integer translation because $\gcd(50,1987)=1$. A careless proof might establish only one of the two invariances, which would yield periodicity modulo $50$ but not constancy. The second delicate step is passing from the constant increment relation

c(n+50)-c(n)\equiv\varepsilon

$$to the affine formula$$

c(n)\equiv an+b.

The coefficient $a$ must satisfy

50a\equiv\varepsilon\pmod3.

Because $50\equiv2\pmod3$ and $2$ is invertible modulo $3$, such an $a$ exists and is nonzero. Without checking invertibility modulo $3$, the affine representation would not be justified. The final contradiction depends on the arithmetic fact

2037=3\cdot679.

$$Substituting into$$

c(n+2037)-c(n)\equiv a\cdot2037

gives zero modulo $3$. Since the original condition requires $n$ and $n+2037$ to have different colors, equality of colors is impossible. ## Alternative Approaches A graph-theoretic proof is possible. Construct a graph whose vertices are the integers and whose edges join pairs of integers whose difference is $50$, $1987$, or $2037$. The condition is equivalent to requiring a proper $3$-coloring in which every triangle is colored with all three colors. Choosing one edge of length $50$ fixes the colors of its endpoints, and the triangle condition then propagates the coloring uniquely through the connected graph generated by $50$ and $1987$. This forces a coloring of the form $c(n)\equiv an+b\pmod3$. A second approach uses group theory. View the coloring as a map from $\mathbb Z$ to $\mathbb Z/3\mathbb Z$. The triangle condition implies that translation by $50$ acts as addition of a fixed nonzero element of $\mathbb Z/3\mathbb Z$. Since $50$ generates $\mathbb Z/3\mathbb Z$, the coloring becomes a homomorphism modulo an additive constant. The fact that $2037$ is divisible by $3$ then forces translation by $2037$ to act trivially on colors, contradicting the requirement that numbers at distance $2037$ have different colors. The main solution makes the propagation mechanism explicit and keeps all steps elementary.