Library / /30 of 30

, 2023

Combinatorics Difficulty 9.1 IMO level Prove it Saudi Arabia

Let $n > 3$ be an integer. Suppose that $n$ children are arranged in a circle, and $n$ coins are distributed between them (some children may have no coins). At every step, a child with at least 2 coins may give 1 coin to each of their neighbours on the right and left. Determine all initial distributions of coins from which it is possible that, after a finite number of steps, each child has exactly one coin.

Solution

The answer is: all distributions where $\sum_{i=1}^n i c_i = \frac{n(n+1)}{2} \pmod n$ , where $c_i$ denotes the number of coins the $i$ -th child starts with.

Encode the sequence $c_i$ as polynomial $p(x) = \sum_i a_i x_i$ . The cyclic nature of the problem makes it natural to work modulo $x^n - 1$ . Child $i$ performing a step is equivalent to adding $x^i(x-1)^2$ to the polynomial, and we want to reach the polynomial $q(x) = 1 + x + \dots + x^{n-1}$ .

Since we only add multiples of $(x-1)^2$ , this is only possible if $p(x) = q(x)$ modulo the ideal generated by $x^n - 1$ and $(x-1)^2$ , i.e.
$(x^n - 1, (x-1)^2) = (x-1)\left(\frac{x^n - 1}{x-1}, (x-1)\right) = (x-1) \cdot (n, (x-1))$
This is equivalent to $p(1) = q(1)$ (which simply translates to the condition that there are $n$ coins) and $p'(1) = q'(1) \pmod n$ , which translates to the invariant. We also could show that this condition is also sufficient. $\square$

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 and solution reproduced as published; topic and difficulty added by this site.