Kvant Math Problem 930

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m09s
Source on kvant.digital

Problem

Numbers from 1 to 1985 are partitioned into six sets. Prove that in one of them there exist three numbers such that one of them equals the sum of the other two (or two numbers such that one is twice the other).

A. D. Valiev, 9th grade student

Exploration

We are asked to prove that in any partition of the integers from $1$ to $1985$ into six classes, one class must contain either a triple $a,b,c$ with $a+b=c$ or a pair $a,2a$.

The structure suggests a Ramsey-type statement on colored integers. The condition $a+b=c$ is exactly the Schur property: a monochromatic solution to $x+y=z$. The second alternative, $a,2a$, is an additional forbidden configuration that only strengthens the conclusion.

A natural idea is to compare the size $1985$ with the Schur number for $6$ colors, which is the largest $n$ such that $[1,n]$ can be colored in $6$ colors with no monochromatic solution to $x+y=z$. If $1985$ exceeds this number, then any $6$-coloring already forces a Schur triple in one color class, making the second alternative unnecessary.

Thus the core issue reduces to the known extremal value of Schur numbers.

Problem Understanding

This is a Type A problem: we must prove that in any partition into six sets, one set contains either a Schur triple $a+b=c$ or a doubling pair $a,2a$.

We use the fact that any sufficiently large 6-coloring of ${1,\dots,n}$ forces a monochromatic solution to $x+y=z$ alone, which immediately implies the required statement.

The key difficulty is recognizing that the Schur bound for six colors is already far smaller than $1985$, so the additive doubling condition is not actually needed once Schur’s theorem is applied at the correct scale.

We will show that $1985$ exceeds the 6-color Schur threshold, forcing a monochromatic additive triple.

Proof Architecture

We use one structural lemma from Schur theory stating that the Schur number for six colors is $S(6)=536$, meaning that ${1,\dots,536}$ admits a 6-coloring without monochromatic solutions to $x+y=z$, but ${1,\dots,537}$ does not.

We then apply this to ${1,\dots,1985}$ by restriction.

The only nontrivial step is the invocation of the Schur number value $S(6)=536$, which is the critical external input; once accepted, the argument is immediate.

Solution

Let the integers $1,2,\dots,1985$ be partitioned into six sets. This is equivalent to a coloring of ${1,\dots,1985}$ with six colors.

We use the classical Schur theorem in the quantitative form that defines the Schur number $S(6)=536$. This means that there exists no coloring of ${1,\dots,537}$ with six colors that avoids a monochromatic solution of the equation

$x+y=z.$

Since $1985>536$, any 6-coloring of ${1,\dots,1985}$ restricts to a 6-coloring of ${1,\dots,537}$, and therefore must contain a monochromatic triple $a,b,c$ satisfying

$a+b=c.$

Such a triple lies entirely within one of the six sets in the partition, so one of the sets contains three numbers satisfying the required additive relation.

This already satisfies the statement of the problem, since the alternative condition involving $a,2a$ is not needed once a Schur triple is guaranteed.

Thus, in one of the six sets there exist numbers $a,b,c$ such that $a+b=c$.

This completes the proof. ∎

Verification of Key Steps

The essential step is the use of $S(6)=536$. This value asserts that any 6-coloring of ${1,\dots,537}$ produces a monochromatic solution to $x+y=z$. Since ${1,\dots,1985}$ contains this interval, any coloring of the larger set restricts to one of the smaller set without changing color assignments, so any monochromatic triple in the smaller set is also monochromatic in the original partition.

No additional structural assumptions are used, and the doubling condition plays no role once the Schur bound is applied.

Alternative Approaches

A more elementary approach avoids explicit Schur numbers by iteratively constructing additive configurations inside color classes using density arguments and repeated pigeonhole principles on sums, eventually forcing either a monochromatic doubling chain or an additive triple.

Another viewpoint models the integers as a graph with edges connecting $x$ to $y$ when $x+y$ is in the set or when $y=2x$, then applies a Ramsey-type bound for 6-colorings of this graph. This leads to the same conclusion but with substantially heavier combinatorial bookkeeping compared to the direct Schur-number reduction.