Maths Olympiad Prep

Library / /9 of 9

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it Switzerland

Problem:

Let n3n \geq 3 be an integer. Annalena has infinitely many cowbells in each of nn different colours. Given an integer mn+1m \geq n+1 and a group of mm cows standing in a circle, she is tasked with tying one cowbell around the neck of every cow so that every group of n+1n+1 consecutive cows have cowbells of all the possible nn colours. Prove that there are only finitely many values of mm for which this is not possible and determine the largest such mm in terms of nn.

Solution

Solution:

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

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

1,1,2,3,,n,1,1,2,3,,n,,1,1,2,3,,nr times,1,2,3,,n,1,2,3,,n,,1,2,3,,nkr times \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)+(kr)n=kn+r=mr(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=n2n1m = n^{2} - n - 1. Observe that n2n1=n(n1)1n^{2} - n - 1 = n(n-1) - 1. By pigeonhole principle, one of the nn colours appears at most n2n-2 times, say blue. Pick an arbitrary cow with a blue bell. There exist now n2n2=(n+1)(n2)n^{2} - n - 2 = (n+1)(n-2) other cows among which only at most n3n-3 wear a blue cowbell. If we partition the remaining cows into intervals of length n+1n+1, we can see that in at least one of them, there is no cow with a blue cowbell.

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.