Let $n>2$ be a positive integer. Masha writes down $n$ natural numbers along a circle. Next, Taya performs the following operation: Between any two adjacent numbers $a$ and $b$, she writes a divisor of the number $a+b$ greater than $1$, then Taya erases the original numbers and obtains a new set of $n$ numbers along the circle. Can Taya always perform these operations in such a way that after some number of operations, all the numbers are equal? Proposed by T. Korotchenko
Problem
Source: All-Russian MO 2024 10.8
Tags: number theory, number theory proposed
24.04.2024 23:24
Claim 1. If every pair doesn’t sum to a power of two, we are done. Just make all the numbers odd on the first turn and after turn them into 2s. Now, firstly, we make all the numbers big enough. Assume there still exists a pair that sum to 2^x, where x is very big. Exchange this pair by a variable P and sum all the other pairs. Keep summing for a few more turns. Now, every number is a linear combination of a few numbers from before, including P. By varying P we can make sure that none of the current sums are powers of two and then finish by claim1.
11.09.2024 22:36
The answer is yes. Let a default operation mean that Taya writes down $a+b$ between any $a,b$. Claim: If a default operation doesn't produce any powers of $2$, we're done. Proof: Instead of performing a default operation, write an odd number everywhere. Then turn them into $2$s in the next operation. Now perform one default operation to make all numbers at least $2$. If the sum of elements is not $n$ times a power of $2$ we stop, otherwise perform another default with one change: in some power of two $2^k$ formed, write $2^{k-1}$ instead. The result is that the sum of elements will not be $n$ times a power of $2$ (for size reasons). Now let the numbers be $a_1,\ldots,a_n$ in order along the circle, with indices taken modulo $n$. After we perform $N$ default moves, the $i$-th number along the circle (with a suitable choice of starting position) will be equal to $$\sum_{j=0}^N \binom{N}{j} a_{i+j}$$by a simple induction. For each $k$, the coefficient of $a_k$ is thus of the form $\sum_{0 \leq nj+r \leq N} \binom{N}{nj+r}$ for some $r$. We estimate the value of this sum: by a roots of unity filter on $\frac{1}{x^r}(1+x)^N$ it equals $$\frac{1}{n}\sum_{j=0}^{n-1} \frac{(1+\omega^j)^N}{\omega^{rj}}=\frac{1}{n}\left(2^N+\sum_{j=1}^{n-1} \frac{(1+\omega^j)^N}{\omega^{rj}}\right),$$where $\omega=e^{2\pi i/n}$. For $j \neq 0$, we have $|1+\omega^j|<2$, so this expression is asymptotically $\frac{1}{n}2^N$ (as a function of $N$). Therefore, for any $\varepsilon>0$ there exists a large enough $N$ such that after $N$ default moves all numbers on the circle are in the interval $$\left[\frac{(1-\varepsilon)2^N}{n}(a_1+\cdots+a_n),\frac{(1+\varepsilon)2^N}{n}(a_1+\cdots+a_n)\right],$$but if $a_1+\cdots+a_n$ isn't $n$ times a power of two then for small enough $\varepsilon$ this interval won't contain any powers of $2$, at which point we can apply the claim to finish. $\blacksquare$