riddle of the day

Five numbers, two colors, and a single rule about sums. There seem to be many ways to distribute the colors, but every choice immediately constrains the next ones.

Five Numbers, Two Colors

Strategist
Master plays

Riddle statement

Color each of the numbers

\{1,2,3,4,5\}

red or blue.

A coloring is valid if there are no numbers \(x,y,z\) of the same color satisfying:

x+y=z.

The numbers \(x\) and \(y\) are allowed to be equal. For example, the relation

1+1=2

must also obey the rule.

Does a valid coloring exist?

Also determine whether \(5\) is the first impossible size: can \(\{1,2,3,4\}\) be colored validly?

Show solution

Solution

Answer: the numbers from \(1\) through \(5\) cannot be colored validly.

Moreover, \(5\) is the first size for which this becomes impossible.

1. Fix the color of 1

The labels “red” and “blue” are interchangeable.

We may therefore assume without loss of generality that:

$ 1\text{ is red}. $

If a solution existed with \(1\) blue, exchanging the names of the two colors would produce one with \(1\) red.

2. The first sums force three colors

Since:

$ 1+1=2, $

the number \(2\) cannot be red, or all three entries in the equation would be red.

Therefore:

$ 2\text{ is blue}. $

Now use:

$ 2+2=4. $

Since \(2\) is blue, \(4\) cannot be blue. Thus:

$ 4\text{ is red}. $

Next:

$ 1+4=5. $

Both \(1\) and \(4\) are red, so \(5\) cannot be red:

$ 5\text{ is blue}. $

The forced colors are now:

$ \begin{array}{c|ccccc} \text{Number} & 1&2&3&4&5\\ \hline \text{Color} & R&B&?&R&B \end{array} $

3. Neither color works for 3

Only \(3\) remains uncolored.

Suppose 3 is red

Then:

$ 1+3=4, $

and \(1,3,4\) are all red.

This violates the rule.

Suppose 3 is blue

Then:

$ 2+3=5, $

and \(2,3,5\) are all blue.

This also violates the rule.

The number \(3\) can be neither red nor blue, a contradiction.

Therefore:

$ \boxed{ \{1,2,3,4,5\}\text{ has no valid coloring} }. $

4. Is five the first impossible case?

Yes.

For:

$ \{1,2,3,4\}, $

use the coloring:

  • red: \(\{1,4\}\);
  • blue: \(\{2,3\}\).

The only relevant sums whose result does not exceed \(4\) are:

$ 1+1=2, $
$ 1+2=3, $
$ 1+3=4, $
$ 2+2=4. $

Checking them:

  • \(1_R+1_R=2_B\);
  • \(1_R+2_B=3_B\);
  • \(1_R+3_B=4_R\);
  • \(2_B+2_B=4_R\).

No equation has all three entries in the same color.

Thus \(1,2,3,4\) admit a valid coloring, but adding \(5\) makes every coloring fail.

5. The corresponding Schur number

The largest integer \(n\) for which:

$ \{1,2,\ldots,n\} $

can be colored with two colors without creating a monochromatic solution of \(x+y=z\) is the Schur number for two colors.

This puzzle proves:

$ \boxed{S(2)=4}. $

Key idea: a few equations create a chain of forced colors. Once the color of \(1\) is fixed, the colors of \(2\), \(4\), and \(5\) are forced, and the two equations involving \(3\) eliminate both of its possible colors.