There are $m \geq 3$ positive integers, not necessarily distinct, that are arranged in a circle so that any positive integer divides the sum of its neighbours. Show that if there is exactly one $1$, then for any positive integer $n$, there are at most $\phi(n)$ copies of $n$. Proposed By- (usjl, adapted from 2014 Taiwan TST)
Problem
Source: IMOC 2021 N4
Tags: number theory
15.08.2021 18:52
Claim 1. Consecutive numbers are coprime. Proof. If two consecutive numbers are divisible by $d>1$, by simple induction we have all numbers divisible by $d$, which contradicts that there is an $1$. Claim 2. The largest number is sum of its two neighbors, and after deleting the largest number, the remaining sequence is still valid. Proof. It is proved in the original problem ; the exception is that its two neighbors are also the largest numbers, which cannot happen due to claim 1. Using claim 2, we can repeatedly delete the largest number from the sequence, until only $3$ numbers remains. Claim 2 implies that the remaining $3$ numbers are $1,a,a+1$ for some integer $a \ge 2$. Reverse this operation, the sequence can be reconstructed based on the remaining $3$ numbers: In the $k$-th round ($k=1,2,\ldots$), we can insert $k$ between two numbers whose sum is $k$ (we are not enforced to insert $k$ between all pairs of such numbers). That is to say, after the $k \ge a+1$-th round, the largest number on the circle is at most $k$. (Actually, there is nothing to do in the first $a$ rounds.) Claim 3. Given any coprime integers $a<b$, they appears consecutively on the circle for at most twice. Proof. Induction on rounds that defined above. Initially, there are only $3$ numbers, the claim is true. Right after the $(a+1)$ th round, there can be at most two consecutive $(1,a+1)$ and $(a,a+1)$, so the claim is true. Now consider after the $n \ge a+2$ th round, i.e. some $n$s are inserted (and there is no $n$ before the round, because $n \ge a+2$). Clearly, this insertion will not increase the number of consecutive $(a,b)$ where $a \neq n, b \neq n$. As for $b=n$, if $(a,n)$ is consecutive on the circle, claim 2 shows that the other neighbor of $n$ is $n-a$, thus $(a,n-a)$ is consecutive before the $n$ th round. By induction hypothesis, it happens at most twice. Back to the main problem, consider the sequence after $n$ th round, i.e. when all $n$s are inserted. Each $n$ on the circle has two neighbor $k$ and $n-k$ for some $1 \le k< \frac{n}{2}$ and $\gcd(k,n)=1$. By claim 3, the number of $n$ is no more than $\varphi(n)$.