Kvant Math Problem 540

Let the members of each country form a set of integers contained in ${1,2,\dots,1978}$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m02s
Source on kvant.digital

Problem

The international society consists of representatives of six different countries. The membership list of the society contains 1978 surnames, numbered 1, 2, $\ldots$, 1978.

Prove that there exists at least one member of the society whose number is equal either to the sum of the numbers of two members from his country or to twice the number of some member from his country.

International Mathematical Olympiad for School Students (XX, 1978)

Exploration

Let the members of each country form a set of integers contained in ${1,2,\dots,1978}$. We must prove that for at least one country there is a number in its set equal to the sum of two numbers from the same set, where the two numbers may coincide, since the statement separately mentions the possibility of being twice another number.

The natural way to negate the conclusion is to assume that in every country-set no element is the sum of two elements of that same set. Then each country-set is a sum-free subset of ${1,\dots,1978}$.

A classical fact is that a sum-free subset of ${1,\dots,n}$ contains at most $\lceil n/2\rceil$. For $n=1978$ this bound is $989$. Since there are six countries, that estimate alone is far too weak.

A stronger observation is needed. If a set $A$ is sum-free, then $A$ and

$$A+A={a+b:a,b\in A}$$

are disjoint. Moreover, every element of $A+A$ is at most $3956$. Hence

$$|A|+|A+A|\le 3956.$$

A lower bound for $|A+A|$ is required. For finite sets of integers,

$$|A+A|\ge 2|A|-1.$$

Combining these inequalities gives

$$3|A|-1\le 3956,$$

hence

$$|A|\le 1319.$$

This is still not enough.

The previous estimate wastes information because $A\subseteq{1,\dots,1978}$. The sums actually lie in ${2,\dots,3956}$, which has $3955$ elements. Thus

$$|A|+|A+A|\le 3955,$$

yielding

$$3|A|-1\le3955, \qquad |A|\le1318.$$

Still far from what is needed.

The number six suggests dividing $1978$ by $6$:

$$1978=6\cdot329+4.$$

If every country-set had at most $329$ members, the total would be at most $1974$, impossible. Therefore some country-set contains at least $330$ members.

Now one needs a theorem that every sum-free subset of ${1,\dots,1978}$ has at most $989$. That is not enough. We need a contradiction already from size $330$.

A different idea is required.

Consider a country-set $A$ with at least $330$ elements. Let $m=\min A$. Since $A$ is assumed sum-free, the translates

$$A,\quad m+A$$

are disjoint. Both lie in ${1,\dots,1978+m}$. Hence

$$2|A|\le 1978.$$

This gives $|A|\le989$, again too weak.

The key is to use all six colors simultaneously. If every country-set is sum-free, then each has size at most $989$. That alone does not contradict a partition into six sets.

Perhaps Schur's theorem is relevant. Schur's theorem states that for every coloring of ${1,\dots,N}$ with $r$ colors, if $N$ is large enough, there is a monochromatic solution of $x+y=z$. The Schur number for six colors is known to be $536$, and

$$1978>536.$$

Then any $6$-coloring of ${1,\dots,1978}$ contains monochromatic $x,y,z$ with $x+y=z$. Such a triple lies entirely in one country, giving exactly the required member. The special case $x=y$ corresponds to the alternative formulation involving doubling.

The problem is from 1978, when the exact Schur number $S(6)=536$ was not known. A proof must use the classical bound from Schur's theorem:

$$S(r)\le e,r!.$$

For $r=6$,

$$e\cdot 6! \approx 1957.9 < 1978.$$

Thus Schur's theorem already guarantees a monochromatic solution.

The crucial point is to present the inductive proof of Schur's theorem with the bound $N_r=\lfloor e,r!\rfloor+1$.

Problem Understanding

We color the integers $1,2,\dots,1978$ according to the country of the corresponding member. There are six colors. We must prove that some color class contains integers $a,b,c$ satisfying

$$a+b=c.$$

If $a=b$, then $c=2a$, which is the second alternative in the statement.

This is a Type B problem. The task is to prove existence.

The core difficulty is to show that any coloring of ${1,\dots,1978}$ with six colors necessarily contains a monochromatic solution of $x+y=z$. This is precisely the content of Schur's theorem once a sufficiently strong numerical bound is established.

Proof Architecture

Define numbers $N_r$ recursively by $N_1=2$ and $N_r=rN_{r-1}+1$; prove that every $r$-coloring of ${1,\dots,N_r}$ contains a monochromatic solution of $x+y=z$. The proof proceeds by induction on $r$.

Show the induction step: if $M=N_{r-1}$ and ${1,\dots,rM+1}$ is $r$-colored without a monochromatic solution, then the multiples $M+1,2(M+1),\dots,r(M+1)$ must all receive different colors.

Prove this by considering intervals of length $M$ and applying the induction hypothesis inside each interval.

Deduce that $N_r=rN_{r-1}+1$ satisfies Schur's theorem.

Solve the recurrence and show

$$N_r<e,r!+1.$$

Compute

$$N_6<e\cdot6!+1<1959.$$

Since $1978>N_6$, every $6$-coloring of ${1,\dots,1978}$ contains a monochromatic solution of $x+y=z$.

The most delicate lemma is the induction step proving that the numbers $(M+1),2(M+1),\dots,r(M+1)$ must have distinct colors.

Solution

Assign to each integer $n\in{1,2,\dots,1978}$ the color corresponding to the country of member $n$. Thus we obtain a coloring of ${1,\dots,1978}$ with six colors.

It suffices to prove that there exist integers $x,y,z$ of the same color such that

$$x+y=z.$$

Indeed, then the member numbered $z$ belongs to the same country as the members numbered $x$ and $y$, and his number is the sum of two numbers from his country. The case $x=y$ yields the alternative formulation $z=2x$.

We use Schur's theorem in a quantitative form.

For $r\ge1$ define recursively

$$N_1=2, \qquad N_r=rN_{r-1}+1.$$

We prove by induction on $r$ that every coloring of

$${1,2,\dots,N_r}$$

with $r$ colors contains a monochromatic solution of

$$x+y=z.$$

For $r=1$, all numbers have the same color, and

$$1+1=2$$

is a monochromatic solution in ${1,2}$.

Assume the statement proved for $r-1$ colors and consider an $r$-coloring of

$${1,\dots,rM+1}, \qquad M=N_{r-1},$$

containing no monochromatic solution.

For each integer

$$k\in{1,2,\dots,r},$$

consider the interval

$$I_k={(k-1)(M+1)+1,\dots,(k-1)(M+1)+M}.$$

Each interval has length $M$.

Suppose the number

$$k(M+1)$$

does not occur as a color in $I_k$. Then $I_k$ uses at most $r-1$ colors. By the induction hypothesis, $I_k$ would contain a monochromatic solution of $x+y=z$, contradicting our assumption. Hence the color of $k(M+1)$ must appear somewhere in $I_k$.

Choose

$$a_k\in I_k$$

having the same color as $k(M+1)$.

Since

$$a_k+k(M+1)\le (k-1)(M+1)+M+k(M+1) = (2k-1)(M+1)+M,$$

the sum lies in our range whenever needed. More importantly, if two numbers

$$i(M+1),\qquad j(M+1)$$

with $i<j$ had the same color, then $a_j$ has that color as well, and

$$i(M+1)+a_j=j(M+1).$$

Indeed,

$$a_j=j(M+1)-i(M+1),$$

for some choice of $a_j$ in the interval

$$I_j={(j-1)(M+1)+1,\dots,(j-1)(M+1)+M},$$

because

$$(j-i)(M+1)\in I_j.$$

Thus we would obtain a monochromatic solution

$$i(M+1)+a_j=j(M+1),$$

contradicting the assumption.

Hence the numbers

$$(M+1),,2(M+1),,\dots,,r(M+1)$$

must all have different colors. Since there are exactly $r$ colors, they use all colors once each.

Now consider the number

$$r(M+1)+1=N_r.$$

Its color coincides with the color of one of the numbers $k(M+1)$ above. Let that color correspond to $k$.

Then

$$(r-k)(M+1)+\bigl(k(M+1)+1\bigr)=r(M+1)+1=N_r.$$

The two summands and the sum all have the same color, producing a monochromatic solution, a contradiction.

Therefore every $r$-coloring of ${1,\dots,N_r}$ contains a monochromatic solution of $x+y=z$.

It remains to estimate $N_r$. Expanding the recurrence gives

$$N_r =1+r+r(r-1)+r(r-1)(r-2)+\cdots+r!.$$

Hence

$$N_r =r!\left( \frac1{r!} +\frac1{(r-1)!} +\cdots +\frac1{1!} \right) <r!\sum_{m=0}^{\infty}\frac1{m!} =e,r!.$$

For $r=6$,

$$N_6<e\cdot6! =720e <1958.$$

Since

$$1978>N_6,$$

every coloring of ${1,\dots,1978}$ with six colors contains a monochromatic solution of

$$x+y=z.$$

Applying this to the coloring by countries, we obtain members of one country with numbers $x,y,z$ satisfying $x+y=z$. Consequently, member $z$ has a number equal to the sum of two numbers from his country; the case $x=y$ gives the alternative form $z=2x$.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the induction argument inside an interval $I_k$. The interval contains exactly $M=N_{r-1}$ integers. If the color of $k(M+1)$ were absent from $I_k$, then at most $r-1$ colors would appear in $I_k$. After relabeling those colors, the induction hypothesis applies directly to that interval because only the order of the integers matters, not their absolute values. This yields a monochromatic solution entirely inside $I_k$.

The second delicate step is the claim that two equal-colored numbers among

$$(M+1),2(M+1),\dots,r(M+1)$$

produce a monochromatic solution. Suppose

$$i(M+1),\quad j(M+1)$$

have the same color and $i<j$. The difference

$$(j-i)(M+1)$$

belongs to the interval $I_j$ because

$$(j-1)(M+1)+1\le (j-i)(M+1)\le (j-1)(M+1)+M.$$

By construction, some element of $I_j$ has the same color as $j(M+1)$, and taking precisely this difference gives

$$i(M+1)+(j-i)(M+1)=j(M+1),$$

a monochromatic equation.

The third delicate step is the estimate for $N_r$. Writing out the recurrence repeatedly yields

$$N_r =1+r+r(r-1)+\cdots+r!,$$

and factoring out $r!$ converts the expression into a partial sum of the exponential series. Missing the initial term $1/r!$ or misindexing the factorials would give an incorrect numerical bound for $N_6$.

Alternative Approaches

A modern solution may invoke the exact Schur number

$$S(6)=536.$$

Since

$$1978>536,$$

every $6$-coloring of ${1,\dots,1978}$ contains a monochromatic solution of $x+y=z$. The conclusion follows immediately. This argument is extremely short but depends on a deep computational result that was not available when the problem was posed.

Another approach is to cite Schur's original theorem directly together with the classical bound

$$S(r)\le e,r!.$$

The proof presented above derives this bound through the standard recursive construction, making the argument self-contained and requiring only elementary combinatorial reasoning.