For $n(n\geq3)$ positive intengers $a_1,a_2,\cdots,a_n$. Put the numbers on a circle. In each operation, calculate difference between two adjacent numbers and take its absolute value. Put the $n$ numbers we get on another ciecle (do not change their order). Find all $n$, satisfying that no matter how $a_1,a_2,\cdots,a_n$ are given, all numbers on the circle are equal after limited operations.
Problem
Source: 2018 China Northern MO, Grade 11, Problem 4
Tags: absolute value, combinatorics
23.02.2020 07:44
We claim that the answer is all powers of two. First let's show that these numbers work. We need to show that, regardless of what $a_1, a_2, \cdots, a_n$ are initially, the numbers on the circle are eventually all zero. First of all, notice that it suffices to solve the problem with the following modifications. Firstly, we'll assume that the numbers are initially relatively prime. If, at any point, the numbers on any of the new circles are not relatively prime, we will divide them all by their greatest common divisor. With this modification, we're ready to solve the problem. First of all, observe that the maximum number in the circle never increases throughout our operation. Hence, we just need to show that it cannot be eventually constant. In order to do this, we will show that the numbers on the circle cannot remain relatively prime forever, which would finish because then the maximum would decrease upon dividing by the greatest common divisor. To show that this is the case, suppose the contrary. Then, simply consider the scenario $n$ moves into the future. By looking modulo $2$, using Pascal's Identity, and using the fact that $\binom{n}{i}$ is even for $1 \le i \le n-1$, it becomes apparent that all numbers are even at this point. Hence, they're not relatively prime and we're done. Now let's show that all $n$ which are not powers of two do not work. We will begin by showing that odds do not work. Indeed, simply start by letting $a_1 = 1$ and all the other numbers be $2$. Then, it's easy to check that at any point after the first instant, there are an even number of $1$'s and an odd number of $0$'s. It's clear that for the numbers to all become $0$, all numbers would have to be $1$ in the previous circle. However, this circle would then have an odd number of $1$'s, contradiction. Now, we'll show that if $n = k$ doesn't work, then neither does $2k.$ The key observation is that, modulo $2$, if we consider $a_1, a_3, \cdots, a_{2k-1}$, then the numbers corresponding to $a_2, a_4, \cdots, a_{2k}$ on the circle which is "two circles later" is $a_1 + a_3, a_3 + a_5, \cdots, a_{2k-1} + a_1.$ Hence, we can now see that if we select $a_1, a_3, \cdots, a_{2k-1}$ such that one is $1$ and the others are $2$, then the circle will never be all zeroes. $\square$