16
$\begingroup$

Positive integers $x_1, x_2, \dots, 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 + \dots + k_n < 3n. $$

This is a problem from some olympiad but I don't remember. What I did was like this :

Let $x_1$ be the smallest. Then obviously, $k_1\ge 2$. I tried to proceed inductively, but then I have no idea. I know it is not something useful, but I lack in any kind of idea. If I try induction, three new terms come replacing three previous terms. Which seems complicated and I can't do anything with it.

Sorry for such a bad try, but I seriously don't have any idea about it. Maybe something ingenious is required here. I hope someone can help. Thanks.

EDIT : Removed meaningless ramblings of mine. Apologies.

$\endgroup$
13
  • $\begingroup$ There is something I cannot grasp. What about the sequence $1,3,5,12$? In this case $\sum k_i = 20 = 5n$. $\endgroup$ Jul 19, 2014 at 17:02
  • $\begingroup$ We also need $12\mid 5+1$ but that is not happening. @JackD'Aurizio Am I correct? $\endgroup$
    – shadow10
    Jul 19, 2014 at 17:08
  • $\begingroup$ Yes, you are right for sure. Sorry. $\endgroup$ Jul 19, 2014 at 17:38
  • $\begingroup$ The lower bound is an easy consequence of the rearrangement inequality: en.wikipedia.org/wiki/Rearrangement_inequality $\endgroup$
    – user940
    Jul 19, 2014 at 17:42
  • 1
    $\begingroup$ @ByronSchmuland could you show how the lower bound follows from rearrangement? Thanks a lot. $\endgroup$
    – shadow10
    Jul 20, 2014 at 5:27

4 Answers 4

5
$\begingroup$

The lower bound only:

Update: I just realized there is an easier argument. The terms in the sum $\sum_i x_{i+1}/x_i$ are just the reciprocals of the terms in the sum $\sum_i x_{i-1}/x_i$. Therefore, our sum $\sum_i k_i$ can be expressed as the sum of $n$ terms of the form $y+{1\over y}.$ Since $y+{1\over y}\geq 2$ for all positive $y$, we get $\sum_i k_i\geq 2n.$


This is exercise 5.7(a) from The Cauchy-Schwarz Master Class by J. Michael Steele. Let $y_i$ be your values $x_i$ only put in order so that $y_1\leq y_2\leq \cdots \leq y_n$. Then the reciprocals are in the opposite order $1/y_n\leq 1/y_{n-1}\leq \cdots \leq 1/y_1$. The lower bound in the rearrangement inequality says that $$n={y_1\over y_1}+{y_2\over y_2}+\cdots+{y_n\over y_n} \leq {y_1\over y_{\sigma(1)}}+{y_2\over y_{\sigma(2)}}+\cdots +{y_n\over y_{\sigma(n)}},$$ for any permutation $\sigma$.

For the appropriate permuations $\sigma$ we get $n\leq \sum_i x_{i-1}/x_{i}$ and $n\leq \sum_i x_{i+1}/x_{i}$ where the index runs cyclically: $\dots,n,1,2,\dots,n-1,n,1,\dots$. Adding these together gives $$2n\leq \sum_i {x_{i-1}+x_{i+1}\over x_i}.$$

$\endgroup$
2
  • $\begingroup$ Nice. I feel the urge to point out that you actually didn't use the divisibility property and integrality of $x_i$. Are these assumptions actually needed? Perhaps a viable approach would be to prove an unconditional weaker upper bound and work from there? $\endgroup$ Jul 22, 2014 at 19:25
  • 1
    $\begingroup$ We can violate the upper bounds with integers: 1,1,1,4. So the divisibility (or some substitute) is needed. $\endgroup$
    – user940
    Jul 22, 2014 at 19:28
5
$\begingroup$

I'm going to reformulate the problem in a slightly more convenient way (I rename $k_i-2$ as $k_i$).

Consider a sequence $\{(x_i,k_i)\}_{i=1}^n\subset \mathbb{R}^+\times \mathbb{Z}$ such that $$ x_ik_i=(x_{i+1}-x_i)-(x_{i}-x_{i-1}). $$ Prove that $0\leq \sum_{i=1}^nk_i<n.$

Upper Bound:

Since $x_i(k_i+2)=x_{i+1}+x_{i-1}>0$, each $k_i\geq -1$. Also notice that $\sum_{i=1}^n x_ik_i=0$. If $k_i=0$ for all $i$, we are done. Thus we may assume $k_1=-1$ without loss of generality.

Induct on $n$, starting at $n=2$. In this case we have $$ \{(2x,-1),(x,2)\},\qquad \mbox{ and }\sum_{i=1}^2 k_i=1<2. $$

Now consider the sequence $\{(x_i,k_i)\}_{i=1}^n$ where $k_1=-1$. Then $x_1=x_2+x_n$; substituting into the $i=2$ and $i=n$ equations yields the sequence $$ \{(x_i',k_i')\}_{i'=1}^{n-1}=\{(x_2,k_2-1),(x_3,k_3),\cdots,(x_{n-1},k_{n-1}),(x_n,k_n-1)\}. $$ Observe that the new sequence is still valid. Applying the inductive hypothesis, $$ \sum_{i=1}^n k_n = (-1) + \sum_{i=2}^n k_n = 1 + \sum_{i=1}^{n-1} k_n' < 1 + (n-1) = n. $$

Lower Bound: Apply AM-GM as follows. $$ \sum_{i=1}^nk_i=\sum_{i=1}^n\left(\frac{x_i}{x_{i+1}}+\frac{x_{i+1}}{x_{i}}-2\right)\geq 0. $$

$\endgroup$
4
+500
$\begingroup$

The lower bound is a simple consequence of the rearrangement inequality, as Byron pointed out. So I will focus on the upper bound.

We will proceed by induction. Call sum of k's as S.

Base case: For n = 2, suppose the numbers are a and b. If a = b, then S = 2 + 2 = 4. Else, let a < b. b|2a, so b = 2a. This gives S = 4 + 1 = 5 < a * 3 = 6. So base case is all good.

Induction case: Suppose the condition holds till n. For the n+1 case, consider the largest element in the array. If there are multiple such elements, take any one of them. Call this m. Let the elements on either side of this maximum be a and b. If either a or b is m, then two things can happen:

1) Either the other one is also m 2) Or the other one is 0

0 is ruled out by the wording of the question (anyway, 0 does not divide sum of positive numbers). So both have to be m. Continuing this way, all elements have to be same. The condition is clearly satisfied in this case.

So we are left with the case where both a and b are less than m. So their sum is less than 2m. In other words, m = a + b. Suppose the elements beyond a and b are respectively c and d. In other words, the part of the array around a + b looks like this:

...c, a, a+b, b, d...

a|(a+b+c), so a|(b+c). Similarly, b|(a+b+d). So b|(a+d).

What this means is that we can go from this array to another valid array with (a+b) removed:

...c, a, b, d...

Now, what is the contribution to S by this a+b? 1 from a+b = 1(a+b). Let a+d=pb. Then (a+b+d)=(p+1)b. Similarly, let b+c=qa. Then (a+b+c)=(q+1)a.

So 1 is added to the k's corresponding to each of a and b by the addition of a+b. This is in addition to the 1 in the k corresponding to (a+b) itself.

So total increase = 3.

Because of this, by induction, if S for n < 3n, then S for (n+1) < 3n + 3 = 3(n+1).

$\endgroup$
6
  • $\begingroup$ Your base case is invalid. Assume WLOG that $a\leq b$. One requires $k_1=2b/a$ and $k_2=2a/b$ to both be integers. Then $k_1 k_2 =4$, so either $a=b=2$ or $a=1,b=4$. But the second case gives $k_2=1/2$ which is not an integer. So only $a=b=1$ is allowed. $\endgroup$ Jul 24, 2014 at 14:00
  • $\begingroup$ "either a=b=2 or a=1,b=4" is wrong. Actual cases are (modulo common factors and reordering) a=b=1 and a=1, b=2. Second case does give S = 4 + 1 = 5. $\endgroup$
    – Wonder
    Jul 24, 2014 at 14:02
  • $\begingroup$ I'm being silly, I meant $k_1=k_2=2$ or $k_1=1$, $k_2=4$. I withdraw the objection. $\endgroup$ Jul 24, 2014 at 14:03
  • $\begingroup$ BTW I did not notice this earlier because the answer was downvoted, but r9m's solution is essentially correct. Just the base case is left out. $\endgroup$
    – Wonder
    Jul 24, 2014 at 14:07
  • 1
    $\begingroup$ That was my downvote: he originally included a claim that his proof implied an upper bound of $3n-2$. But that's false since you can take $\{1,2,3,\ldots,n\}$ to get $3n-1$. (I hadn't noticed that he's since withdrawn that, so I've removed my -1.) $\endgroup$ Jul 24, 2014 at 14:10
4
$\begingroup$

Lower bound: Am-Gm inequality: $\displaystyle \sum\limits_{i=1}^n k_i = \sum\limits_{i=1}^n {\dfrac{x_i}{x_{i+1}}}+\dfrac{x_{i+1}}{x_i} \ge 2n$

Upper bound: We can show by strong induction on $n$ that, $\displaystyle \sum\limits_{i=1}^n k_i < 3n$

Suppose, $\exists \,n_0 (\ge 2)$, such that $\displaystyle \sum\limits_{i=1}^{n_0} k_i < 3n_0$.

For $n > n_0$, we may assume that not all $x_i$'s are equal (in which case $\displaystyle \sum\limits_{i=1}^n k_i = 2n$), so that there is a $j$ for which $x_j \ge x_{j-1}$ and $x_j \ge x_{j+1}$, with a strict inequality in atleast one of these two.

So, $2x_j > x_{j-1} + x_{j+1}$, and hence $k_j = 1$.

Thus, the cyclic arrangement with $x_j$ removed also satisfies the given conditions, with $k_{j-1}$ and $k_{j+1}$ both decreased by $1$, and $k_j$ removed.

Since, the sum of resulting $n-1$, $k_i$'s does not exceed $3(n-1)$ (by, induction hypothesis), $\implies \displaystyle \sum\limits_{i=1}^n k_i < 3n$.

We need to check the base case $n_0$.

The establish the base case, $n_0 = 4$, we make an argument similar as above and assume not all $x_1,x_2,x_3,x_4$ are equal and wlog that $2x_4 > x_1 + x_3$, implying $k_4 = 1$. Which brings it down to $k_1' = \dfrac{x_2 + x_3}{x_1}$, $k_2 = \dfrac{x_1+x_3}{x_2}$ and $k_3' = \dfrac{x_1+x_2}{x_3}$. Again if we assume not all $x_1,x_2,x_3$ are equal (equality leads to $k_1'+k_2+k_3' = 6$), that is wlog $2x_3 > x_1+x_2$, which leaves us to prove $\dfrac{2x_1}{x_2}+\dfrac{2x_2}{x_1} < 6$, where $p=\dfrac{2x_1}{x_2},q=\dfrac{2x_2}{x_1}$ are integers.

Hence, $p+\dfrac{4}{p} = 4,5 < 6$ depending on $p=1,2,4$. Thus the base case holds.

$\endgroup$
4
  • $\begingroup$ As noted by @ByronSchmuland in the comments, the sequence $\{1,2,3,\ldots,n-1,n\}$ gives a sum of $3n-1$ which violates your supposed bound. $\endgroup$ Jul 24, 2014 at 4:56
  • $\begingroup$ @Semiclassical so the problem lies in the base case !! :o $\endgroup$
    – r9m
    Jul 24, 2014 at 4:58
  • $\begingroup$ I understand "thus, the cyclic arrangement with $x_j$ removed also satisfies the given conditions" by direct checking. You must have come to this conclusion more intuitively. Could you please share your insight? $\endgroup$
    – Hans
    Jul 27, 2014 at 17:07
  • $\begingroup$ @Hansen The key step for me was observing that $k_j \in \mathbb{Z}^{+}$ forces $x_j = x_{j-1} + x_{j+1}$, for the first $j$ which differs from at least one of its neighbours (in the case $\sum\limits_{i=1}^n k_i > 2n$). This linear relation should suggest substituting $x_j$ in the expressions for $k_{j-1}$ and $k_{j+1}$ (that is where ever $x_j$ appears in that $\sum k_i$ in order to reduce the number of variables involved), and observe that it fits the pattern for an induction argument as you verified :) $\endgroup$
    – r9m
    Jul 27, 2014 at 18:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .