does this problem require any unknown lemma or something like that?

No, the solution is totally elementary. It's a very nice problem IMO, probably one of my favorite medium-easy combinatorics problems.

http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=553283

http://www.artofproblemsolving.com/Forum/viewtopic.php?p=731752&sid=aeba4bc571d32cd71802e6560b528741#p731752

What is the motivation for using induction and looking at the maximal element? Thanks in advance! (By the way, isn't this more algebra than combinatorics)

^ Jacob Tsimerman wrote: Induction is awesome and should be used to its full potential Arthur Engel wrote: ...the extremal principle, which has truly universal applicability Here's a proof which shows $\sum k_i \leq 3n-1$, by induction on $n$. The base case $n=4$ can be established by hand. For $n>2$, assume the $x_i$ are not all equal. Then we can find some $i$ such that $x_i \geq x_{i-1},x_{i+1}$, where at least one of the inequalities is strict. It follows that in this case, $k_i=1$. We conclude that the sequence with $x_i$ removed also satisfies the given condition with $k_{i-1},k_{i+1}$ decreased by $1$, and $k_i$ dropped. Since the sum of the resulting $k_i$ is at most $3n-4$ by the induction hypothesis, the sum of the original $k_i$ is at most $3n-1$, as required.

I think you mean $3n-1$ because the sequence $x_1=1, x_2=2, ..., x_n=n$ gives $k_1+k_2+...+k_n=3n-1$.

Just curious, why do we need $n\ge 4$? It seems that the problem makes perfect sense for $n=3$ and its true in that case. Also, here is my solution (similar to above posts):

yayups wrote: Just curious, why do we need $n\ge 4$? It seems that the problem makes perfect sense for $n=3$ and its true in that case. Yeah, I'm not sure. You're right that the problem is fine for $n=3$.

We have \[ \sum_{i=1}^n k_i = \sum_{i=1}^n \frac{x_{i-1}}{x_i} + \frac{x_i}{x_{i-1}} \ge \sum_{i=1}^n 2 = 2n\]by AM-GM. Suppose not all the $x_i$'s are equal (this case is trivial). We induct on $n$ to show the upper bound. Consider the $i$ with $x_i$ maximal. We claim $k_i=1$. Suppose $k_i\ge 2$. Then $2x_i \le x_{i-1}+x_{i+1}$, which means at least one of $x_{i-1},x_{i+1}$ greater than or equal to $x_i$. Then there must exist at least one maximal $x_i$ not equal to both its neighbors, and this is a contradiction. Hence some $i$ satisfies $k_i=1$, so $x_i=x_{i-1}+x_{i+1}$. Delete $x_i$. We claim what remains is a valid sequence. The list of $x_i$'s looked like \[ (\ldots,x_{i-2}, x_{i-1}, x_{i-1}+x_{i+1}, x_{i+1}, x_{i+2},\ldots). \]So we know $x_{i-1} \mid x_{i-2} + x_{i-1}+x_{i+1}$ and $x_{i+1} \mid x_{i-1}+x_{i+1}+x_{i+2}$. After deletion, the list is \[ (\ldots,x_{i-2}, x_{i-1}, x_{i+1},x_{i+2},\ldots). \]We have $x_{i-1} \mid x_{i-2}+x_{i+1}$ and $x_{i+1}\mid x_{i-1}+x_{i+2}$ from the divisibilty condition earlier. Hence the sequence remaining is valid. Furthermore, note that the sum of the $k_i$'s decreased by 3 after deletion. The sum of the remaining $k_i$'s is then at most $3n-3$ by induction. Adding back in the $x_i$ increases this sum by at most 3, completing the induction.

Lower bound: Trivial by AM-GM. Upper bound: The idea is to induct downward by deleting the maximal $x_i$. Base case: It is easy to see that the bound holds for $n=4$. Inductive step: If all the $x_i$ are equal then we're done; otherwise, choose $i$ such that $x_i$ is maximal and is not equal to both its neighbors. Then, we have $k_i=1$, and $x_i=x_{i-1}+x_{i+1}$. Next note that $k_{i-1}=\frac{x_{i-2}+x_i}{x_{i-1}}=\frac{x_{i-2}+x_{i-1}+x_{i+1}}{x_{i-1}}=1+\frac{x_{i-2}+x_{i+1}}{x_{i-1}}$, and similarly, $k_{i+1}=1+\frac{x_{i-1}+x_{i+2}}{x_{i+1}}$. Thus, $x_{i-1}|x_{i-2}+x_{i+1}$ and $x_{i+1}|x_{i-1}+x_{i+2}$, meaning that after we delete $x_i$, we still have a valid sequence. So now delete $x_i$; note that in the sequence of $k_j$, the only change is that the three terms $k_{i-1}, k_i, k_{i+1}$ is replaced with the two terms $\frac{x_{i-2}+x_{i+1}}{x_{i-1}}, \frac{x_{i-1}+x_{i+2}}{x_{i+1}}$, which are equal to $k_{i-1}-1, k_{i+1}-1$. Since $k_i=1$, we thus have that by deleting $x_i$, we obtain a new valid sequence with $n-1$ terms, where the sum of all the $k_j$ is 3 less than that of the sequence with $n$ terms. By inductive hypothesis, we are done.

To prove the left hand side of the inequality, notice that$$\sum_{i=1}^n k_i = \frac{x_{i-1}}{x_i} + \frac{x_{i+1}}{x_i} = \sum_{i=1}^{n} \frac{x_{i-1}}{x_i} + \frac{x_{i}}{x_{i-1}} \ge 2 \times n = 2n$$as desired. The right hand side is much more tricky, but the idea is to induct. First, notice that for all $i$, we have $x_{i-1} + x_{i+1} = k_i x_{i}$. This means that if we sum over all $i$, then$$\sum_{i=2}^{n+1} x-{i-1} + x_{i+1} = \sum_{i=1}^n k_i x_i.$$If we take $k_i \ge 2$ for all $i$, then$$2(x_1 + x_2 + \dots x_n) = k_1 x_1 + k_2 x_2 + \dots k_n x_n \implies (k_1 - 2)x_1 + (k_2-2)x_2 + \dots (k_n - 2)x_n = 0.$$Clearly if $k_i \ge 2$, then equality only holds when all of the $k_i$ are set to $2$, for which we have $k_1 + \dots + k_n = 2n.$ Otherwise, $(k_1 - 2)x_1 + (k_2-2)x_2 + \dots (k_n - 2)x_n > 0$, which means that the given cannot hold. Therefore, there must exist a $k_i$ satisfying $k_i = 1$. WLOG let $k_1 = 1.$ The sequence now becomes$$\{x_{n} + x_{2}, \dots x_n, x_{n} + x_{2}, x_{2}, \dots \}.$$Claim: If we delete term $x_1$, the remaining sequence is still valid. Proof: In the original sequence, we must have $x_{2} \mid x_{n} + x_2 + x_3 \implies x_2 \mid x_n + x_3,$ which also holds if $x_1$ is deleted. Similar reasoning holds for most other cases. Now, we will induct. The base case $n = 4$ is easily seen. Notice that, upon deletion of $x_1$, we also are deleting $\frac{x_1 + x_{3}}{x_2}, \frac{x_n + x_2}{x_1}$, and $\frac{x_{n-1} + x_1}{x_n},$ and replacing these by $\frac{x_{n} + x_{3}}{x_2},$ and $\frac{x_{n-1} + x_{2}}{x_n}.$ Now, note that $\frac{x_{n-1} + x_1}{x_n} = \frac{x_{n-1} + x_{2}}{x_n} + 1,$ $\frac{x_1 + x_{3}}{x_2} = \frac{x_{n} + x_{3}}{x_2} + 1$, and we are also adding $k_1 = 1$ to the sum of the previous $k_n$, meaning we add at most $3$ to the sum, completing the induction.

Finally found the source for this nice problem. For the lower bound, note that AM-GM yields $\frac{x_i}{x_{i+1}} + \frac{x_{i+1}}{x_i} \geq 2$ for each $1 \leq i \leq n$, and summing all the inequalities gives the desired bound. The upper bound is the pith of the problem. The case $n=4$ can be checked by hand, as there are only a finite number of sequences that satisfy the problem condition, up to scaling. Now we induct on $n$. Note that if all the $x_i$ are equal the sum is $2n$, so we can assume that there exists a maximal element, say $x_j$, such that at least one of its neighbors isn't equal to $x_j$. Note now that $x_{j-1} + x_{j+1} = x_j.$ I claim that removing $x_j$ yields a valid sequence. Note that by removing $x_j,$ we remove $k_j = 1$ from the sum. Moreover, $k_{j-1}$ and $k_{j+1}$ get decreased by $1$, so the total sum is decreased by $3$. This completes the induction.

The lower bound is just by AM-GM, thus holds when all the $x_i$ are equal. For the upper bound, the idea is that we can delete the largest term and get a circle that still works. Each deletion removes 3 from the k-sum, which will allow us to finish by induction. The one weird case is when there are two equally largest terms that are consecutive; however, one can check that this case either leads to a contradiction by extremal or just gives every single term equal. Now, assume WLOG that $x_1$ is the largest term. Then, $x_n + x_2 = k_1x_1$. If $k_1 > 1$, then at least one of $x_n$ and $x_2$ is geq $x_1$, which leads to one of the contradictions stated above. Thus $k_1 = 1$, and deleting this removes $1$ from the sum. Next, write $k_2x_2 = x_1 + x_3$ and $k_nx_n = x_1 + x_{n-1}$. After the deletion of $x_1$, we get a new $k_2'$ and $k_n'$ terms, given by $k_n' = \frac{x_2 + x_{n - 1}}{x_n}$ and $k_2' = \frac{x_3 + x_n}{x_2}$. Add $x_1 = x_n + x_2$ to $k_2x_2 = x_1 + x_3$ to get $$k_2x_2 = x_n + x_2 + x_3 \implies k_2' = \frac{x_3 + x_n}{x_2} = k_2 - 1.$$Repeat this for the other equation and we are done.

The LHS is true by AM-GM. Now, we use induction to prove the RHS, the case $n=4$ is easy. Observe that the RHS is clearly true when the $x_i$ are all equal. $\qquad (\star)$ From $(\star)$, we can assume that the $x_j$ are not all equal. Then, we choose the $x_i$ with maximum value. Due to size reasons, $k_i \leq 2$. Furthermore, if $k_i=2 \implies max\{x_{i-1},x_{i+1}\} \geq x_i$, but since $x_i$ is maximum, $max\{x_{i-1},x_{i+1}\}=x_i \implies x_{i-1}=x_{i+1}=x_i$ $\implies$ since the $x_j$ are not all equal, we repeat this algorithm until we find a $x_j$ such that $k_j=1$, because $x_{i-1}=x_i=x_{i+1}=...=x_j$ with maximum value, but this is impossible, because $x_{j-1}=x_j$ with maximum value implies $x_{j+1}=x_j$ $\implies$ all numbers are equal, a contradiction by assumption. Hence, $k_i=1 \implies x_i=x_{i-1}+x_{i+1} \implies x_i-x_{i-1}=x_{i+1}|x_i+x_{i+2} \implies x_{i+1}|x_{i-1}+x_{i+2}$ and similarly $x_{i-1}|x_{i+1}+x_{i-2} \implies$ since $k_{i+1}'=\frac{x_{i-1}+x_{i+2}}{x_{i+1}},k_{i-1}'=\frac{x_{i+1}+x_{i-2}}{x_{i-1}} \geq 1=k_i$ and $ \frac{(\sum_{i=1}^n k_i)-k_i-k_{i-1}-k_{i+1}+k_{i-1}'+k_{i+1}'}{n-1} \geq \frac{\sum_{i=1}^n k_i}{n}$ , we can delete $x_i$ and induct downwards. $\blacksquare$

To prove the lower bound, we note that \begin{align*} \sum_{i=1}^n k_i & = \sum_{i=1}^n \frac{x_{i-1} + x_{i+1}}{x_i}\\ & = \sum_{i=1}^n \frac{x_{i-1}}{x_i} + \frac{x_{i+1}}{x_i}\\ & = \sum_{i=1}^n \frac{x_{i-1}}{x_i} + \frac{x_{i}}{x_{i-1}}\\ & \ge \sum_{i=1}^n 2\\ & = 2n \end{align*} by AM-GM. To prove the upper bound, we use induction. We notice that the problem works for degenerate cases as well - in particular $n=2$. To prove the upper bound for $n=2$, we note that the condition says that $x_1\text{ } |\text{ } 2x_2$ and $x_2\text{ } |\text{ } 2x_1$. If $x_1 > x_2$, the first divisibility implies that $2x_2 = x_1,$ which works. The case $x_1 < x_2$ is similar. Since the upper bound clearly holds for $x_1 = x_2$, this completes the base case. For our inductive step, assume that the problem holds for $n-1 \ge 2$. We will show that this implies the claim for $n$. Let $x_m$ be the maximum of all the $x_i$'s. Then we notice that $k_m$ is at most $2$. We proceed with two cases. $\textbf{Case 1:}$ $k_m = 1$ In this case, we have $x_{m-1} + x_{m+1} = x_m$. We also have $x_{m-2} + x_{m} = k_{m-1}x_{m-1}$ and $x_{m} + x_{m+2} = k_{m+1}x_{m+1}$. Consider removing $x_m$ from the circle. We claim that this will result in a value sequence of $x_i$'s. To see this, we note that \[k_{m+1}x_{m+1} = x_m + x_{m+2} = x_{m-1} + x_{m+1} + x_{m+2}\] and \[k_{m-1}x_{m-1} = x_{m-2} + x_m = x_{m-2} + x_{m-1} + x_{m+1}.\] These simplify to \[(k_{m+1}-1)x_{m+1} = x_{m-1} + x_{m+2}\] and \[(k_{m-1}-1)x_{m+1} = x_{m-2} + x_{m+1}\] respectively. Since $x_m > x_{m-1}, x_{m+1}$, both of $k_{m-1}, k_{m+1}$ are at least $2$. Then removing $x_m$ from the circle does indeed result in a valid sequence. Moreover, the net loss in the sum of the $k_i$'s is three, so the claim is true by the inductive step. $\textbf{Case 2:}$ $k_m = 2$ In this case, we must have $x_{m-1} = x_m = x_{m+1}$. Then $k_{m-1}$ is at least $2$, since the $x_i$'s are all positive integers. By the maximality of $x_m$, we must have $x_{m-2} = x_m$ as well. Repeating this process yields that all of the $x_i$'s are equal, which clearly results in a configuration satisfying the constraints. We have exhausted all cases, so this completes the problem. $\square$

The lower bound is immediate by AM-GM; we will work on the upper bound. Suppose that the largest element on the circle is equal to x_m. It's easy to show that k_m<=2. If k_m=2, we have that the numbers adjacent to x_m are equal to x_m; from here, it's easy to get that the entire circle consists of equal numbers, meaning that the sum of k_i's is equal to 2n. If k_m=1, then we can remove the largest element; k_{m-1} and k_{m+1} also decrease by 1 in the process, so the sum of k_i's decrease by 1 by removing the largest element. Repeating this act will eventually lead us to reach either a circle of 2 numbers or a circle with equal numbers. The latter case obviously would have the average less than 3, and we can solve to get x_1=2x_2 or x_2=2x_1 in the former case, which would make k_1+k_2=5<6.

The lower bound is just AM-GM, so it suffices to prove that $k_1+\cdots+k_n\leq 3n-1$. We extend the problem to degenerate cases with $n<4$. For $n=1$, we find that $k_1=\tfrac{x_1+x_1}{x_1}=2=3-1$, which fits. Now suppose that $n-1$ works. Consider the index $i$ such that $x_i$ is maximal. If there are multiple, pick one such that its neighbors aren't both equal to $x_i$ as well—if no such $i$ exists, then we have $k_i=2$ for all $i$ and the inequality clearly holds. Then it is clear that $k_i<2 \implies k_i=1 \iff x_i=x_{i-1}+x_{i+1}$. Now delete $x_i$; it is easy to verify that the remaining integers still divide the sum of their neighbors, and moreover the new values of $k_{i-1}$ and $k_{i+1}$ are each one less than the old, so the value of the desired sum increases by $3$, preserving the inequality. $\blacksquare$

The lower bound is just the inequality $\frac{x}{y} +\frac{y}{x} \geq 2$ applied 2 times. For the upper bound, consider the element of largest value. If there is another element with the same value next to it, then all of them have the same value and we get the equality case for the lower bound. Thus the elements next to it are smaller and sum up to it's own value. Notice that when we remove it we are left with a valid example with $n-1$ elements and the desired sum decreases by 3. We continue to remove elements in such fashion until we can't no more, either because there are too little elements(only 3) left, or all of them have become equal. But we can easily show the inequality in these cases, so we're done.

We claim the statement also holds for $1\le n\le 3$. Note that the lower bound is just AM-GM. For the upper bound, we proceed by induction on $n$. The base case $n=1$ is clear. For the inductive step, consider $x_1,x_2,\dots,x_m$. If all of $x_i$ are equal, then the upper bound clearly holds so let $x_j$ be a maximum element such that $x_{j-1},x_{j+1}<x_j$. Note $j$ exists as if $x_i$ and $x_{i+1}$ are consecutive maximums, $x_{i+2}=x_{i+1}k_{i+1}-x_i$ has to also be a maximum, which inductively means that all $x_i$ are maximums, a contradiction. Notice $2x_j>x_{j-1}+x_{j+1}$ so $x_j=x_{j-1}+x_{j+1}$. Removing $x_j$, we see that we lose $k_j$ and $k_{j-1}$ decreases by $1$ as \[\frac{x_{j-2}+x_{j+1}}{x_{j-1}}=\frac{x_{j-2}+x_{j+1}+x_{j-1}}{x_{j-1}}-1=\frac{x_{j-2}+x_j}{x_{j-1}}-1\]Similarly, $k_{j+1}$ decreases by $1$. By the inductive hypothesis, the sum of $k_i$ for all sequences with length $m-1$ is less than $3(m-1)$, so the sum of $k_i$ for our sequence with $m$ terms is less than $3(m-1)+3=3m.$ Thus, our induction is complete. $\square$

First we will prove that the sum is always greater than or equal to $2n$. Since $\frac{x_i}{x_{i+1}}+\frac{x_{i+1}}{x_i}$ is greater than or equal to $2$ by AM-GM, we have that our summation of $k_i$‘s is greater than or equal to $2n$ and we are done here. Now we set to prove the upper bound. First take the maximum value in the sequence $x_n$. WLOG assume that it is $x_1$. Notice that we must have that $k_1=1$ because otherwise by Pigeonhole we would no longer have our number be the largest possible. Now we may use induction to proceed. Let $x_1=a+b$, $x_n=a$, and $x_2=b$. Notice that from here, by substituting in this value in the equation for $n=k+1$ and subtracting $3$ from both sides, we are left with the equation for $k$. Now we must just prove the base case of $n=3$. Notice we will have $a$, $b$, and $a+b$. We would like to prove that $\frac{2a}{b}+\frac{2b}{a}<6$, where $\frac{2a}{b}$ and $\frac{2b}{a}$ are integers. Let $\frac{a}{b}$ be equal to $\frac{k}{2}$ for some integer $k$. Now we are left with $k+\frac{4}{k}<6$ for some integer $k$. Since our maximum value occurs at $k=1$, this equation is true and we are done.

The lower bound is just AM-GM. For the upper bound, we have the following: Claim. There exists an index $i$ such that $x_i = x_{i-1} + x_{i+1}$. Proof. Assume otherwise. Find some two indices $x_1, x_2$ with $x_1 < x_2$. Then, the claim implies $$x_1 + x_3 \geq 2x_2 \implies x_3 > x_2.$$In a similar fashion, the $x_i$ must be strictly increasing, but this is a contradiction by cyclicity. $\blacksquare$ Now we induct. The base case $n=4$ is easy to verify. Without loss of generality let this index be $x_n$. Notice that $$\frac{x_1 + x_{n-1}}{x_n} = \frac{x_{n+1} - x_n + x_{n-1}}{x_n} = \frac{x_{n+1} + x_{n-1}}{x_n} - 1,$$and a similar equality holds for the other side. This implies that the maximum possible sum of $k_i$'s with $n+1$ indices is at most three more than the maximum possible sum of $k_i$'s with $n$ indices, which is enough.

Note that the lower bound clearly follows from $AM-GM$: \[\sum_{i=1}^n k_i = \sum_{i=1}^n \frac{x_{i-1}+x_{i+1}}{x_i} = \sum_{j=1}^n \frac{x_{j-1}}{x_j} + \frac{x_j}{x_{j-1}} \geq \sum_{j=1}^n 2 = 2n\] For the upper bound, consider the largest element $x_m=M$. Note that $\frac{x_{m-1}+x_{m+1}}{x_m}\leq 2$. If the $\frac{x_{m-1}+x_{m+1}}{x_m}= 2$ equality holds, then $x_{m-1} = x_m = x_{m+1}$. Thus, there is some block of $M$s. If it encompasses the entire circle, then the sum of $k_i$s is $2n$, and if it doesn't, we derive a contradiction because then there is a $(\cdots M,M,x,\cdots)$ sequence which fails because $M\nmid M+x$ for $x<M$. Either way, the sum of $k_i$s is clearly less than $3n$ if $\frac{x_{m-1}+x_{m+1}}{x_m}= 2$. We now consider the other case, when $x_m = x_{m-1}+x_{m+1}$. Then, we may in fact use strong induction on $\sum_{i=1}^n k_i<3\cdot n$. This is because when we remove $x_m$, the decrease has size \begin{align*} &\left(\frac{x_{m-2}+x_m}{x_{m-1}} + \frac{x_{m-1}+x_{m+1}}{x_m} + \frac{x_m + x_{m+2}}{x_{m+1}}\right)- \left(\frac{x_{m-2}+x_{m+1}}{x_{m-1}}+\frac{x_{m-1} + x_{m+2}}{x_{m+1}}\right)\\ &= \frac{x_m-x_{m+1}}{x_{m-1}} + \frac{x_{m-1}+x_{m+1}}{x_m}+ \frac{x_m -x_{m-1}}{x_{m+1}} = 1+1+1=3 \end{align*}Thus, by doing casework on the $k_m$ value of the maximum value $x_m = M$, we have shown that the sum of $k_i$ is less than $3n$ through strong induction and we are done. $\blacksquare$.

Denote \[ r_i := \frac{x_i}{x_{i-1}}. \]By AM-GM, \[ \sum k_i = \sum \left(r_{i+1} + \frac{1}{r_i}\right) = \sum \left(r_i + \frac{1}{r_i}\right) \ge 2n, \]proving the lower bound. To prove the upper bound, we induct downwards on $n \ge 5$, with the base case $n=4$ verifiable by hand. Assume henceforth that not all of the $x_i$ are equal. Claim: Let $x_j$ be a maximal element. Then $x_j = x_{j-1}+x_{j+1}$. Proof. Assume for contradiction that $x_{j-1}+x_{j+1} \ge 2x_j$. Then by pigeonhole, at least one of $x_{j-1}$ and $x_{j+1}$ are greater than or equal to $x_j$. If that is the case, then one of $x_{j-1}$ and $x_{j+1}$ (WLOG $x_{j+1}$) is equal to $x_j$. Now $x_{j+1} \mid x_{j+2}$, so $x_{j+2} \ge x_{j+1}$. Inducting on the index, we find that all of the $x_i$ must be equal, a contradiction. Thus $x_j = x_{j-1}+x_{j+1}$. Consider a maximal element $x_j$. Then we will show that removing $x_j$ from the arrangement will reduce $\sum k_i$ by at least $3$, which would complete the induction. Consider the $5$ terms $x_{j-2}, \dots, x_{j+2}$. The sum of the $k_i$ that these terms contribute is \[ r_{j+2} + r_{j+1} + r_j + \frac{1}{r_{j-1}} + \frac{1}{r_j} + \frac{1}{r_{j+1}}. \]Removing $x_j$, the contributed sum becomes \[ r_jr_{j+1}+r_{j-1}r_j + \frac{1}{r_{j-1}} + \frac{1}{r_{j+2}}. \]Subtracting and substituting $r_jr_{j+1} = r_j - 1$ returns a delta of \[ -2-r_{j+2}-\frac{1}{r_{j+1}} + \frac{1}{r_{j+2}} = -2-k_{j+2} - \frac{1}{r_{j+2}} \le -3, \]which completes the inductive step.

For the lower bound, we apply AM-GM twice to get $$\begin{aligned} \sum_{i = 1}^nk_i &= \sum_{i = 1}^n \frac{x_{i - 1} + x_{i + 1}}{x_i} \\ &\ge \sum_{i = 1}^n\frac{2\sqrt{x_{i - 1}x_{i + 1}}}{x_i} \\ &\ge 2n. \end{aligned}$$ For the upper bound, we induct on $n$, and show that the problem statement holds for $n = 3$ as well. For the base case of $n = 3$, assume WLOG that $x_1 = \max\{x_1, x_2, x_3\}$. Then because $x_1 \mid (x_2 + x_3)$, we have either $k_1 = 1$ or $k_1 = 2$. If $k_1 = 2$, then we have $x_1 = x_2 = x_3$ so the sum of all $k_i$ is $6$, which is less than $3n = 9$. If $k_1 = 1$, then we wish to prove that $$1 + \frac{x_1 + x_3}{x_2} + \frac{x_1 + x_2}{x_3} < 9 \iff \frac{x_3}{x_2} + \frac{x_2}{x_3} < 3.$$WLOG assume that $x_2 \le x_3$. If $x_2 = x_3$ the inequality is evident. Else, notice that $x_3 \mid (x_1 + x_2) = 2x_2 + x_3$, so $x_3 \mid 2x_2$ and $\tfrac{x_3}{x_2} \le 2$. Since $\tfrac{x_2}{x_3} < 1$, the inequality still holds. For the inductive step, assume the hypothesis holds for $n - 1$. Then for $n$, we assume WLOG that $x_1 = \max\{x_1, x_2, \ldots, x_n\}$. Similar to before, we now find that $k_1 = 1$ or $k_1 = 2$. If $k_1 = 2$, then we find that $x_n = x_2 = x_1$, and then that $x_{n - 1} = x_1 = x_3$, and so on until all of the $x_i$ are equal; this means that all of the $k_i$ sum to $2n$. If $k_1 = 1$, then consider what happens when we remove $x_1$ from the circle. Because $x_n \mid (x_{n - 1} + x_1 - x_n) = x_{n - 1} + x_2$ and similarly $x_2 \mid (x_n + x_3)$, the integers around the circle still satisfy that all of the $k_i$ are integers. However, we now have $$\frac{x_{n - 1} + x_2}{x_n} = \frac{x_{n - 1} + x_1 - x_n}{x_n} = \frac{x_{n - 1} + x_1}{x_n} - 1,$$and similarly $k_2 = \tfrac{x_1 + x_3}{x_2} - 1$. We also disregard $k_1$ now, and none of the other $k_i$ have changed, so the total sum of the $k_i$ has decreased by $3$, and we are done by the inductive hypothesis.

Denote $r_k = \frac{x_k}{x_{k-1}}$. We have \[\sum k_i = \sum (r_{i+1}+\frac{1}{r_i}) = \sum (r_i+\frac{1}{r_i}) \ge 2n,\] proving the lower bound. As for the upper bound, we extend this inequality to degenerate cases i.e. $n<4$. For $n=1$, this inequality holds true so we consider what would happen if we went from $k$ numbers to $k-1$ numbers. Let $x_m$ be the maximal element in the circle. If there is no unique element, pick one such that its neighbors aren't both equal to $x_m$ as well (if no such $i$ exists, then we have $k_i=2$ for all $i$ and the inequality clearly holds). We claim that $x_{m-1}+x_{m+1} = x_m$: FTSOC, suppose $x_{m-1}+x_{m+1} > x_m$, we must have one of them equal to $x_m$, WLOG say $x_{m+1}$. Now, we have that $x_{m+1} \mid x_{m+2}$, so we have reduced the index by one and all of them will be equal by induction, a contradiction to our maximal element condition. Now, if we delete $x_m$ from the circle, it is clear that $k_{m-1}$, $k_m$, and $k_{m+1}$ are going to decrease by $1$, so the entire circle decreases by $3$, and the inequality is preserved. Hence, the upper bound holds true for all $n$ by induction. $\square$

The lower bound follows from straightforward AM-GM. Thus we only need to prove that $k_1 + k_2 + \dots + k_n \le 3n - 1$. WLOG assume $x_1$ is the largest number that written on the circle. Then we can assume $x_2 \neq x_1$. Then $x_n + x_2 < 2x_1$, hence $x_1 = x_n + x_2$. Now erase $x_1$ from the circle. Then the remaining $n-1$ positive integers satisfies the condition. Therefore by inducting down, we're done. $\blacksquare$

Our lower bound can be determined using AM-GM, as \[K = \sum k_i = \sum \left(\frac{a_i}{a_{i+1}} + \frac{a_{i+1}}{a_i}\right) \ge 2n.\] The equality case occurs when all $x_i$ are equal, which also satisfies the upper bound. Otherwise, suppose WLOG $x_n$ is the maximal term such that at least one of $x_{n-1}$ or $x_i$ is strictly less than it. Then we must have \[x_{n-1} + x_1 = x_n \implies k_n = 1.\] If we were to remove $x_n$, the sum $K$ decreases by 3 - one from deleting $k_n$, and one from both $k_{n-1}$ and $k_1$. Thus we can continuing inducting downwards until we either hit our lower bound equality case or the trivial case of $n=2$, where the maximum for $K$ is evidently $5=3 \cdot 2-1$. Hence the maximum of $K$ for $n=n'$ is $3n'-1$, as desired. $\blacksquare$

For the first part, by AM-GM: \[ \sum_{i=1}^n k_i = \sum_{i=1}^n \frac{x_{i-1}}{x_i} + \frac{x_i}{x_{i-1}} \ge \sum_{i=1}^n 2 = 2n\] For the second part: Let the sequence in which each number divide the sum of it's neighbors called "working". at first assume that all $x_i$ are equal. then obviously it satisfy the problem condition. Now assume that not all $x_i$ are the same, we will show that inductively. Claim: Let $x_j$ be the maximal, then $k_j=1$ pf: Assume FTSOC that $k_j \geq 2$, then $2x_j \le x_{j-1}+x_{j+1}$, meaning that at least one of $x_{j+1}$,$x_{j-1}$ is more that $x_j$. Contradiction. So by our claim we have that $x_j = x_{j-1}+x_{j+1}$. substituting this in our sequence: \[ {\dots,x_{j-2}, x_{j-1}, x_{j-1}+x_{j+1}, x_{j+1}, x_{j+2},\dots}. \]Meaning that $x_{j-1} \mid x_{j-1}+x_{j+1}+x_{j-2}$ which implies that $x_{j-1} \mid x_{j+1}+ x_{j-2} $ Applying the same reasoning to $x_{j+1}$, we get that $x_{j+1} \mid x_{j+2}+ x_{j-1} $ Which means that deleting $x_{j-1}+x_{j+1}$ from the sequence gives us another working sequence. Notice that after deleting, $$\sum_{i=1}^n k_i$$decreased by $3$. Adding back $x_i$ meaning that the sum can increase by $3$ at most.

Lower bound is just AM-GM after separating the fraction, with equality where all the terms are equal. The upper bound is more interesting. Claim : max sum is $3n-1.$ To prove this, we induct. Note that the problem works for degenerate cases as well, namely $n=1,2,3.$ For $n=1,$ the problem is trivial, so onto the inductive step. Let $n$ be the largest term in the sequence. Note that if one of the terms adjacent to $n$ is equal to $n,$ then all the terms are $n,$ otherwise, $n$ wouldn't be the maximum. Let the terms adjacent to $n$ be $x$ and $y.$ It is clear that $x+y=n.$ Now, let the term to the left of $x$ be $w$ and to the right of $y$ be $z.$ Then the order of the terms would be $w, x, x+y, y, z.$ The $k$ of the middle three terms is then $$\frac{w+x+y}{x}, 1, \frac{x+y+z}{y},$$respectively. Removing $x+y,$ it turns into only two $k$'s, being $\frac{w+y}{x}, \frac{x+z}{y},$ respectively. This is a change of $-3,$ so we're done.

Cute problem To prove the lower bound, note that $\sum_{i = 1}^n \frac{x_{i - 1} + x_{i + 1}}{x_i} = \sum_{i = 1}^n \left( \frac{x_{i - 1}}{x_i} + \frac{x_i}{x_{i - 1}} \right) \ge 2n$ by AM-GM. Here, indices are cyclic $\pmod{n}$. The upper bound is more involved. We proceed with induction on $n$. For the base case $n = 2$, we want to show that $\frac{2x_2}{x_1} + \frac{2x_1}{x_2} < 6$ where $x_1 \mid 2x_2$, $x_2 \mid 2x_1$. Let $x_1 = 2^a p$ and $x_2 = 2^b q$ where $a = \nu_2(x_1)$, $b = \nu_2(x_2)$. We have $p \mid q$, $q \mid p$ which implies $p = q$, so we want to show $2^{b - a + 1} + 2^{a - b + 1} < 6$. But $a \le b + 1$ and $b \le a + 1$ which imply $-1 \le a - b \le 1$. When $a = b$ the quantity equals $4$, and when $a - b = -1, 1$ it equals $5$. Both are strictly less than $6$. Now we proceed with the inductive step, assume that the upper bound is true for all positive integers $2 \le n \le k$. Consider any sequence $(x_1, x_2, \dots, x_{k + 1})$. WLOG $x_{k + 1}$ is the largest, then using the $n = k$ bound on $(x_1, x_2, \dots, x_k)$ we have $\sum_{i = 1}^k \frac{x_{i - 1} + x_{i + 1}}{x_i} < 3n$ with $\pmod{k}$ indices. To show $\sum_{i = 1}^{k + 1} \frac{x_{i - 1} + x_{i + 1}}{x_i} < 3n + 3$ with $\pmod{k + 1}$ indices it is sufficient to prove that $$\frac{x_{n - 1} + x_{n + 1}}{x_n} + \frac{x_n + x_1}{x_{n + 1}} + \frac{x_{n + 1} + x_2}{x_1} - \frac{x_{n - 1} + x_1}{x_n} - \frac{x_n + x_2}{x_1} \le 3$$$$\iff \frac{x_{n + 1} - x_1}{x_n} + \frac{x_n + x_1}{x_{n + 1}} + \frac{x_{n + 1} - x_n}{x_1} \le 3.$$$\textbf{Case 1.}$ $x_{n + 1}$ equals $x_1$ or $x_n$. WLOG $x_{n + 1} = x_1$. The sum equals $\frac{x_n + x_1}{x_1} + \frac{x_1 - x_n}{x_1} = 2 \le 3$. $\textbf{Case 2.}$ $x_{n + 1} > x_1, x_n$. Since each fraction on the left-hand side is a positive integer we have $x_n \le x_{n + 1} - x_1$ and $x_{n + 1} \le x_n + x_1$ implying that $x_n = x_{n + 1} - x_1$. So plugging this in gives $\frac{x_{n + 1} - x_1}{x_{n + 1} - x_1} + \frac{x_{n + 1} - x_1 + x_1}{x_{n + 1}} + \frac{x_{n + 1} - x_{n + 1} + x_1}{x_1} = 3 \le 3$. We have exhausted all necessary cases, and our induction is complete. We are done!

Left side bound is simply AM-GM. Right side bound: Observe that all $k_i \ge 2$ implies $k_i = 2 \forall i$, and this is the minimum so assume otherwise. Then there exists $i$ with $x_i = x_{i-1} + x_{i+1}$. Put this information into the other expressions containing it, and a simple induction should suffice. (Note: Claim the problem holds for $n \ge 3$ and take base case as $n = 3$ for simplicity.

Fun one. For the LHS ($2n$) bound, simply apply AM-GM to the $2n$ terms of the form $\frac{x_i}{x_{i\pm 1}}$. For the RHS ($3n-1$) bound, we induct with base case $n=1$ where $k_1=2$. If all $x_i$ are equal, then it equals $2n\leq3n-1$. Otherwise, pick one of the maximal $x_c$ such that it's not adjacent to two copies of $x_c$, and it must be the case that $x_c=x_{c-1}+x_{c+1}$. This will result in a valid configuration still, since $x_{c-1}\equiv x_c\pmod{x_{c+1}}$ and similarly $x_{c+1}\equiv x_c\pmod{x_{c-1}}$. The difference is \begin{align*}k_{c-1}+k_c+k_{c+1}-k'_{c-1}-k'_{c+1}&=\frac{x_{c-2}+x_c}{x_{c-1}}+\frac{x_{c-1}+x_{c+1}}{x_c}+\frac{x_c+x_{c+2}}{x_{c+1}}\\&\quad-\frac{x_{c-2}+x_{c+1}}{x_{c-1}}-\frac{x_{c-1}+x_{c+2}}{x_{c+1}}\\&=3.\end{align*}Therefore removing the maximal element changes $\sum k_i$ by $3$, and inducting gives that the maximum $\sum k_i$ is $3n-1$.

First Part: $k_1+k_2 + \dots + k_n = \sum_{i=1}^n k_i=\sum_{i=1}^n \frac{x_{i-1}+x_{i+1}}{x_i} =\sum_{i=1}^n ( \frac{x_{i-1}}{x_i} + \frac{x_i}{x_{i-1}})$ $=\frac{x_n}{x_1}+\frac{x_2}{x_1}+\frac{x_1}{x_2} + \frac{x_3}{x_2} + \dots + \frac{x_{n-1}}{x_n} + \frac{x_1}{x_n} = (\frac{x_1}{x_2} + \frac{x_2}{x_1}) + ( \frac{x_2}{x_3} + \frac{x_3}{x_2}) + \dots + (\frac{x_1}{x_n}+\frac{x_n}{x_1})$ $ \stackrel{AM-GM}{ \geq } \underbrace{2 + 2 + \dots + 2}_{n \text{ terms}} = 2n \implies$ $$ 2n \leq k_1+k_2 + \dots + k_n \square$$ Second part: If $x_1=x_2 = \dots = x_n \iff x_i=x_j \forall i,j: 1\leq i,j \leq n$ then: $k_1+k_2+ \dots k_n = \sum_{i=1}^n k_i=\sum_{i=1}^n \frac{x_{i-1}+x_{i+1}}{x_i}=\sum_{i=1}^n \frac{x_i+x_i}{x_i}=\sum_{i=1}^n \frac{2 x_i}{x_i}=\underbrace{2 + 2 + \dots + 2}_{n \text{ terms}} =2n <3n \implies k_1+k_2+ \dots k_n <3n $ So suppose one of the $x_i$ is different $\forall i \leq n$ WLOG $x_1 \leq x_2 \leq \dots \leq x_n$ So $\text{min}(x_i)=x_1 , \text{max} (x_i)=x_n \forall i : 1 \leq i \leq n$. Note that $x_1 < x_n (\because$ one of the $x_i$ is different) So $k_n=\frac{x_{n-1}+x_{1}}{x_n} < \frac{x_n+x_n}{x_n}= \frac{2 x_n}{x_n}=2 \implies k_n < 2 \implies k_n=1 (\because k_n \in \mathbb{Z^+})$ Hence $1=k_n=\frac{x_{n-1}+x_{1}}{x_n} \implies \boxed{x_n=x_1+x_{n-1}} ... (*)$ Now we prove $k_1 + k_2 + \dots + k_n < 3n$ by using induction. $\textbf{Base Case:}$ $n=2 \implies k_1=\frac{2x_2}{x_1} , k_2=\frac{2x_1}{x_2}$ So $k_1 \cdot k_2=\frac{2x_2}{x_1} \cdot \frac{2x_1}{x_2}=4 \implies k_1 \cdot k_2=4$ Since $k_1>k_2 (\because x_1 <x_2$ and $ x_1 \neq x_2$ ) we get: $k_1=4 , k_2=1$ So $k_1+k_2=4+1=5 <6 \implies k_1+k_2 <6$ $\textbf{Inductive hypothis:}$ Suppose it's true for $n-1$ so: $k_1+k_2+ \dots + k_{n-1} < 3 (n-1) \iff \sum_{i=1}^{n-1} k_i < 3 (n-1)$ $\textbf{Inductive step:}$ Note that $k_n=1$ from before. $k_1+k_2+ \dots + k_{n-1}+k_n=k_1+k_{n-1}+k_n +( k_2+k_3 + \dots + k_{n-2})= k_1+ k_{n-1}+k_n +\sum_{i=2}^{n-2} k_i$ $=\frac{x_n+x_2}{x_1} + \frac{x_{n-2}+x_n}{x_{n-1}} + 1 + \sum_{i=2}^{n-2} k_i \stackrel{ (*) }{ = } \frac{x_1+x_{n-1}+x_2 }{x_1} + \frac{x_{n-2}+x_1+x_{n-1} }{x_{n-1}} + 1 +\sum_{i=2}^{n-2} k_i $ $=1+\frac{x_{n-1}+x_2}{x_1} +1 + \frac{x_{n-2}+x_1}{x_{n-1}} + 1 + \sum_{i=2}^{n-2} k_i =3 +\frac{x_{n-1}+x_2}{x_1} + \frac{x_{n-2}+x_1}{x_{n-1}}+ \sum_{i=2}^{n-2} k_i $ $3 +\sum_{i=1}^{n-1} k_i < 3+ 3(n-1) =3n \implies$ $$k_1+k_2 + \dots +k_n <3n \square $$

I considered the sequence $1, 2 \to 1, 3, 2 \to 1, 4, 3, 5, 2$ as a child so seeing it here is silly. For the lower bound, note that \[ k_1 + k_2 + \dots + k_n \le \sum_{\text{cyc}} \frac{x_i}{x_{i+1}} + \frac{x_{i+1}}{x_{i}} \ge 2n \]follows by AM-GM. For the upper bound, we firt consider $n = 3$. Claim: This holds for $n = 3$. Proof. Let the three integers be $a, b, c$. If all three are equal then the integers are $(x, x, x)$. Else, WLOG let $a \ge b \ge c$ be the largest so since $a \mid b + c$, it follows that $b + c = a$. Then this implies that $b \mid 2c, c \mid 2b$ so either $b = c$ or $b = 2c$, so the integers can be $(2x, x, x)$ or $(3x, 2x, x)$ which work. $\blacksquare$ Now consider the minimal counterexample with $k_1 + k_2 + \dots + k_n \ge 3n$. Claim: Some $k_i = 1$. Proof. Suppose that all $k_i \ge 2$. Then note that \[ \sum_{\text{cyc}} x_{i-1} + x_{i+1} = \sum_{\text{cyc}} k_ix_i \ge \sum_{\text{cyc}} 2x_i \]which implies all $k_i = 2$, contradiction. $\blacksquare$ Now suppose $k_i = 1$. Then we get that $x_i = x_{i-1} + x_{i+1}$. Removing $x_i$ from the circle decreases the sum of $k_i$ by $3$, which gives a smaller counterexample.

$ $