Switzerland — Final Round

Solution:

Let us first give a construction which works for all numbers $m \geq n^{2}-n$:

Write $m = k n + r$ for some integer $k \geq n-1$ and $r \in \{0,1, \ldots, n-1\}$. Note that $k - r \geq 0$. If we call the colours $1,2, \ldots, n$, we arrange them as follows:

$$\underbrace{1,1,2,3, \ldots, n, 1,1,2,3, \ldots, n, \ldots, 1,1,2,3, \ldots, n}_{r \text{ times}}, \underbrace{1,2,3, \ldots, n, 1,2,3, \ldots, n, \ldots, 1,2,3, \ldots, n}_{k-r \text{ times}}$$

Note that $r(n+1) + (k-r)n = k n + r = m$. It is easy to see that this construction indeed works.

We will now prove that it is not possible to accomplish the task for $m = n^{2} - n - 1$. Observe that $n^{2} - n - 1 = n(n-1) - 1$. By pigeonhole principle, one of the $n$ colours appears at most $n-2$ times, say blue. Pick an arbitrary cow with a blue bell. There exist now $n^{2} - n - 2 = (n+1)(n-2)$ other cows among which only at most $n-3$ wear a blue cowbell. If we partition the remaining cows into intervals of length $n+1$, we can see that in at least one of them, there is no cow with a blue cowbell.