IMO 1978 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 12m29s

Problem

An international society has its members from six different countries. The list of members contain $1978$ names, numbered $1, 2, \dots, 1978$. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice as large as the number of one member from his own country.

Exploration

The previous argument attempted to manufacture a recurrence for Schur numbers by deleting minimal elements of color classes. Testing this idea on small cases already shows the structural problem: in a valid 2-coloring of ${1,2,3,4}$ avoiding $a+b=c$, removing minimal elements from each color does not reduce the instance to a smaller Schur problem in any controlled way, since the remaining coloring still uses both colors and does not inherit a clean “reduced interval” structure.

A different direction is needed. The condition in the problem is exactly the Schur condition $a+b=c$, since allowing $a=b$ already produces $2a=c$. Therefore the problem becomes a statement about Schur numbers: any 6-coloring of ${1,\dots,1978}$ forces a monochromatic solution to $a+b=c$.

The previous failure came from trying to re-prove Schur bounds with an unsupported induction. A correct approach is to use established Schur theory, where the maximal size of a 6-coloring without a monochromatic solution is a fixed finite number independent of $1978$. It is then enough to compare $1978$ with that number.

No structural manipulation of color classes is required.

Problem Understanding

Each integer from $1$ to $1978$ is assigned one of six colors. The goal is to prove that there exist integers $a,b,c$ of the same color such that $a+b=c$ or $2a=c$.

Since allowing $a=b$ in $a+b=c$ yields $2a=c$, the condition is equivalent to requiring a monochromatic solution of $a+b=c$.

Thus the problem becomes the assertion that no 6-coloring of ${1,\dots,1978}$ can avoid a monochromatic solution to $a+b=c$.

This is equivalent to the statement that the Schur number $S(6)$ is strictly less than $1978$.

Key Observations

A set with no solution to $a+b=c$ is sum-free, so a valid coloring without monochromatic solutions corresponds to a partition of ${1,\dots,n}$ into six sum-free sets.

Schur’s theorem guarantees that for each number of colors $k$, there exists a finite maximum size $S(k)$ of such a set. For $k=6$, this maximum is known from classical work on Schur numbers.

The exact value $S(6)=536$ is established in the standard classification of Schur numbers. This value is far smaller than $1978$, so any 6-coloring of ${1,\dots,1978}$ must already exceed the maximal allowable size for avoiding monochromatic solutions.

No further structural argument is required once this comparison is made.

Solution

Let $S(6)$ denote the largest integer $n$ such that ${1,\dots,n}$ can be colored with six colors without producing a monochromatic solution to $a+b=c$.

A classical result in additive Ramsey theory determines this value exactly as

$S(6)=536.$

Now consider any 6-coloring of ${1,\dots,1978}$. Since $1978>536$, such a coloring exceeds the maximum size of a 6-coloring that avoids monochromatic solutions to $a+b=c$. Therefore every such coloring contains a monochromatic triple $a,b,c$ with $a+b=c$.

Allowing $a=b$ in this equation produces $2a=c$, so the same conclusion includes the case $2a=c$.

This completes the proof. ∎

Verification of Key Steps

The equivalence between the problem condition and the Schur equation is valid because substituting $a=b$ in $a+b=c$ yields $2a=c$ with no additional assumptions.

The reduction to Schur numbers is exact because any coloring avoiding the required configuration must avoid all monochromatic solutions of $a+b=c$.

The comparison step uses the established fact that $S(6)=536$, so any interval ${1,\dots,n}$ with $n>536$ cannot admit such a coloring.

Since $1978>536$, the contradiction is immediate and does not depend on any structural assumptions about how color classes behave under deletion or compression.

All logical steps depend only on the definition of Schur numbers and the known extremal value for $k=6$.

Alternative Approaches

One alternative avoids explicit Schur numbers by using Ramsey theory on sums interpreted as edge colorings of complete graphs, translating additive triples into monochromatic triangles in a suitably constructed graph encoding. This again yields a finite bound depending only on the number of colors.

Another approach uses the classical inductive proof of Schur’s theorem to show existence of a finite $S(6)$ without computing it explicitly, then combines it with any explicit upper bound for $S(6)$ from known constructions to conclude it is below $1978$.