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$ – Jack D'Aurizio Jul 19 '14 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 '14 at 17:08
  • $\begingroup$ Yes, you are right for sure. Sorry. $\endgroup$ – Jack D'Aurizio Jul 19 '14 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 '14 at 17:42
  • 1
    $\begingroup$ @ByronSchmuland could you show how the lower bound follows from rearrangement? Thanks a lot. $\endgroup$ – shadow10 Jul 20 '14 at 5:27
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$ – Vít Tuček Jul 22 '14 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 '14 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$ – Semiclassical Jul 24 '14 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 '14 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$ – Semiclassical Jul 24 '14 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 '14 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$ – Semiclassical Jul 24 '14 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$ – Semiclassical Jul 24 '14 at 4:56
  • $\begingroup$ @Semiclassical so the problem lies in the base case !! :o $\endgroup$ – r9m Jul 24 '14 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 '14 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 '14 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.