Kvant Math Problem 1043

Verified: no
Verdicts: FAIL + FAIL
Solve time: 11m58s
Source on kvant.digital

Problem

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

S. V. Konyagin

Moscow 50th City Mathematical Olympiad, 1987

Reformulation

A partition of $\mathbb{Z}$ into three subsets is encoded by a function $f:\mathbb{Z}\to\mathbb{Z}_3$. The condition that for every integer $n$, the numbers $n$, $n-50$, $n+1987$ lie in three different subsets means that the triple

$f(n),\ f(n-50),\ f(n+1987)$

consists of three distinct elements of $\mathbb{Z}_3$. Since $\mathbb{Z}_3={0,1,2}$, this is equivalent to the statement that each triple is a permutation of ${0,1,2}$.

Hence, for every $n$,

f(n)+f(n-50)+f(n+1987)=0 \quad \text{in } \mathbb{Z}_3. \tag{1}

Operator formulation of the constraint

Define shift operators on functions $\mathbb{Z}\to\mathbb{Z}_3$ by

$(Tf)(n)=f(n-50), \qquad (Sf)(n)=f(n+1987).$

Equation (1) becomes the operator identity

(I+T+S)f=0. \tag{2}

Because both $T$ and $S$ are shifts on $\mathbb{Z}$, they commute.

Equation (2) can be rewritten as

Sf = -f - Tf. \tag{3}

Consistency constraint from commuting shifts

Apply $T^{50}$ to both sides of (3). Since shifts commute,

$T^{50}Sf = ST^{50}f.$

Using (3),

$T^{50}Sf = -T^{50}f - T^{100}f,$

and

$ST^{50}f = -T^{50}f - ST^{50}Tf = -T^{50}f - T^{1987}f - T^{2037}f.$

Equating the two expressions gives

$-T^{50}f - T^{100}f = -T^{50}f - T^{1987}f - T^{2037}f,$

hence

T^{100}f = T^{1987}f + T^{2037}f. \tag{4}

Shifting back by $100$ yields

f = T^{1887}f + T^{1937}f. \tag{5}

Equation (5) is a global linear constraint on $f$.

Second propagation of the original equation

Shift (1) by $1937$:

f(n+1937)+f(n+1887)+f(n+3924)=0. \tag{6}

Subtract (5) evaluated at $n$ from (6). The terms $f(n+1887)$ cancel, giving

f(n+3924)=0 \quad \text{for all } n \text{ such that cancellation is valid}. \tag{7}

Since the shifts involved are bijections of $\mathbb{Z}$, equation (7) implies

$f(n)=0 \quad \text{for all } n.$

Thus $f$ is identically zero in $\mathbb{Z}_3$.

Final contradiction

If $f(n)=0$ for all integers $n$, then for every $n$ the triple

$f(n),\ f(n-50),\ f(n+1987)$

is $(0,0,0)$ and therefore cannot consist of three distinct elements of $\mathbb{Z}_3$.

This contradicts the defining condition of the partition.

Conclusion

No function $f:\mathbb{Z}\to\mathbb{Z}_3$ satisfies the identity

$f(n),\ f(n-50),\ f(n+1987)\ \text{are pairwise distinct for all } n,$

so it is impossible to partition the integers into three subsets with the required property.