Library / /278 of 383

, 2021

Combinatorics Difficulty 8.8 Shortlist Prove it IMO

Let $n \geqslant 3$ be an integer. An integer $m \geqslant n+1$ is called $n$ -colourful if, given infinitely many marbles in each of $n$ colours $C_{1}, C_{2}, \ldots, C_{n}$ , it is possible to place $m$ of them around a circle so that in any group of $n+1$ consecutive marbles there is at least one marble of colour $C_{i}$ for each $i=1, \ldots, n$ .
Prove that there are only finitely many positive integers which are not $n$ -colourful. Find the largest among them.

Solution

Answer: $m_{\text{max}} = n^{2} - n - 1$ .

First suppose that there are $n(n-1)-1$ marbles. Then for one of the colours, say blue, there are at most $n-2$ marbles, which partition the non-blue marbles into at most $n-2$ groups with at least $(n-1)^{2} > n(n-2)$ marbles in total. Thus one of these groups contains at least $n+1$ marbles and this group does not contain any blue marble.

Now suppose that the total number of marbles is at least $n(n-1)$ . Then we may write this total number as $n k + j$ with some $k \geqslant n-1$ and with $0 \leqslant j \leqslant n-1$ . We place around a circle $k-j$ copies of the colour sequence $[1,2,3, \ldots, n]$ followed by $j$ copies of the colour sequence $[1,1,2,3, \ldots, n]$ .

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 reproduced verbatim; metadata (topic, difficulty) added by this project.