Let n≥3 be an integer. Annalena has infinitely many cowbells in each of n different colours. Given an integer m≥n+1 and a group of m cows standing in a circle, she is tasked with tying one cowbell around the neck of every cow so that every group of n+1 consecutive cows have cowbells of all the possible n colours. Prove that there are only finitely many values of m for which this is not possible and determine the largest such m in terms of n.
Solution
Solution:
Let us first give a construction which works for all numbers m≥n2−n:
Write m=kn+r for some integer k≥n−1 and r∈{0,1,…,n−1}. Note that k−r≥0. If we call the colours 1,2,…,n, we arrange them as follows:
r times1,1,2,3,…,n,1,1,2,3,…,n,…,1,1,2,3,…,n,k−r times1,2,3,…,n,1,2,3,…,n,…,1,2,3,…,n
Note that r(n+1)+(k−r)n=kn+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=n2−n−1. Observe that n2−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 n2−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.
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.