Taiwan TST 2014

Problem: Positive integers $x_1,x_2,...,x_n(n\ge 4)$ are arranged in a circle such that each $x_i$ divides the sum of the neighbors, that is $\frac{x_{i-1}+x_{i+1}}{x_i}=k_i$ is an integer for each $i$, where $x_0=x_n,x_{n+1}=x_1$. Prove that: $2n\le k_1+k_2+...+k_n<3n$.

Solution: We first establish the lower bound. Note that:

$\sum\limits_{i=1}^{n}k_i=\sum\limits_{i=1}^{n}(\frac{x_{i+1}}{x_i}+\frac{x_{i-1}}{x_i})\ge (2n)\sqrt[2n]{1}=2n$, where the inequality is $AM-GM$.

We claim that the upper bound holds for all $n\ge 2$. We proceed by induction on $n$. Consider the base case $n=2$. Here, $k_1=\frac{2x_2}{x_1},$ and $k_2=\frac{2x_1}{x_2}$. Note that $k_1,k_2\in \mathbb{N}$ and $k_1k_2=4$, so either $k_1=4$ and $k_2=1$ or $k_1=k_2=2$. In the first case, we get $(x,2x)$, in the second we get $(x,x)$, both of which work.

Assume the upper bound holds for $n-1$. Now consider the situation for $n$. WLOG, let $x_n$ be the maximum element. There are three cases.

Case 1: $k_n\ge 3$. In this case, $x_1+x_{n-1}\ge 3x_n$. However, this clearly violates the maximality of $x_n$, so this case does not exist.

Case 2: $k_n=2$. In this case, $x_1+x_{n-1}=2x_n$. The only way to not violate maximality of $x_n$ is for $x_{n-1}=x_1=x_n$. However, one quickly sees that this implies that the whole sequence is constant, in which case the average of the $k_is$ is $2$, so this case is resolved.

Case 3: $k_n=1$. Now, $x_n=x_1+x_{n-1}$. Note that:

$\frac{k_1+...+k_n}{n}=\frac{k_1+k_{n-1}+k_n+\sum\limits_{i=2}^{n-2}k_i}{n}$

$=\frac{3+\frac{x_{n-2}+x_1}{x_{n-1}+\frac{x_2+x_{n-1}}{x_1}}}{n}<\frac{3+3(n-1)}{n}=3$, where the inequality follows from the inductive hypothesis. Therefore, our induction, and our proof is complete.

Source: https://artofproblemsolving.com/community/c473124h1546246_more_combinatorics