Maths WorkshopMaths problems with full solutions
Exercise 1094Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

Three same-color integers

#pigeonhole#same color#arithmetic progression

Statement

If 1,2,…,2n1,2,\ldots,2n are colored with 22 colors, show that some two same-color integers differ by nn.

Hint

Consider pairs (1,n+1),(2,n+2),…,(n,2n)(1,n+1),(2,n+2),\ldots,(n,2n): nn pairs, each differing by nn.

Show solutionHide solution

Solution

Pairs. nn pairs, each with difference nn.

Pigeonhole. Color each pair with 22 colors. To avoid a same-color pair, we'd need n≤2n\le 2 (only 22 colors). For n≥3n\ge3, some pair has the same color.

Actually, the simple pigeonhole argument doesn't directly apply: 22 colors across nn pairs doesn't force a same-color pair, since each pair can be different colors.

Better approach. Suppose no pair of same-color integers differs by nn. Then for each pair (i,i+n)(i,i+n), the two colors differ. This forces the coloring pattern: color ii and color i+ni+n are opposite for each i∈{1,…,n}i\in\{1,\ldots,n\}. But then color ii and i+2ni+2n? We only have 2n2n integers.

Conclusion. The statement is true by a parity argument for 22 colors: color classes must pair up to have opposite colors, which is possible. Actually the statement is false: color the first nn red and the last nn blue; then each pair (i,i+n)(i,i+n) has one red, one blue — no same-color pair with difference nn.

Correction. The problem is false as stated. The correct Ramsey-type statement needs different parameters.