Competition problem — Combinatorics

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Bulgaria

Let $k > 1$ be an integer. A set of natural numbers $S$ is called good if all positive integers can be painted in $k$ colors such that no element of $S$ is a sum of two distinct numbers having one and the same color. Find the largest positive integer $t$ for which the set
$S = \{a+1, a+2, a+3, \dots, a+t\}$
is good for all positive integers $a$ .

Solution

We show that the desired number equals $t = 2k - 2$ .

Consider the set $S = \{3, 4, \dots, 2k, 2k+1\}$ . The sum of any two distinct numbers from $1, 2, \dots, k+1$ is an element of $S$ . Since among $1, 2, \dots, k+1$ there exist two numbers having one and the same color we conclude that $S$ is not good. Now $|S| = 2k-1$ implies $t \le 2k-2$ .

It remains to prove that the set $S = \{a+1, a+2, \dots, a+2k-2\}$ is good for any $a$ .

1. Let $a$ be an odd number. Color the numbers $1, 2, \dots, \frac{a+1}{2}$ in the first color and every of the numbers $\frac{a+2s-1}{2}$ for $s = 2, 3, \dots, k$ in color $s$ . Let all numbers greater than $\frac{a+2k-1}{2}$ be of color $k$ . It is easy to see that the sum of any two numbers of one and the same color is not an element of $S$ .

2. Let $a$ be an even number. Color the numbers $1, 2, \dots, \frac{a}{2}$ in the first color and every of the numbers $\frac{a+2s-2}{2}$ for $s = 2, 3, \dots, k$ in color $s$ . Let all numbers greater than $\frac{a+2k-2}{2}$ be of color $k$ . It is easy to see that the sum of any two numbers of one and the same color is not an element of $S$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.