5
$\begingroup$

I ran into nice problem which I proved and would be thankful if anyone assess it.

Given a sequence of integers $x_1, x_2, \dots, x_n$ whose sum is 1? prove that exactly one of the cyclic shifts $$x_1,x_2,\dots, x_n; \quad x_2,\dots, x_n,x_1; \cdots \quad x_n, x_1\dots, x_{n-1}$$ has all of his partial sums positive. (By a partial sum we mean the sum of the first $k$ terms, $k\leqslant n$.)

My solution: For $n=1$ we have a single-term sequence and it is obvious.

Assume that our proposition is true for $n$. We'll try to prove it for $n+1$.

Let we have the sequence $(x_1, x_2, \dots, x_n,x_{n+1})$ then $\exists \ i$ such that $x_i>0$.

  1. If $1\leqslant i <n+1$ then consider the following sequence $(x_1, \dots,x_i+x_{i+1},\dots, x_{n+1})$ which has $n$ elements. Then using the assumption of induction we have that there is exactly one cyclic shift with desired property, And if we write $x_i, x_{i+1}$ instead of $x_i+x_{i+1}$ and since $x_i>0$ we get our desired sequence.

  2. If $i=n+1$, i.e. $x_{n+1}>0$ then replace the sequence $(x_1, x_2, \dots, x_n,x_{n+1})$ by $(x_2, \dots, x_n,x_{n+1}+x_1)$ which consists of $n$ terms. Then using the assumption of induction we get exactly one sequence with desired properties and separating $x_{n+1}+x_1$ to $x_{n+1}, x_1$ we get the sequence with $n+1$ elements since $x_{n+1}>0$.

$\endgroup$
  • $\begingroup$ You have not justified why the cyclic shift you obtain is unique. First of all, there might be more than one $i$ for which $x_i>0$. Second of all, you use the induction hypothesis to obtain a unique cyclic shift of length $n$ with the desired property, but you do not explain why the cyclic shift is still unique when you expand it to one of length $n+1$. $\endgroup$ – kccu Nov 16 '17 at 19:00
  • $\begingroup$ @kccu, yes you are definitely right! I have not shown the uniqueness of $n+1$ sequence. Right now I am thinking about that but no results. Would be grateful if anyone can show the uniqueness. $\endgroup$ – ZFR Nov 17 '17 at 7:26
2
$\begingroup$

As stated in the comments, you're good on the existence part, but you haven't shown the uniqueness. Let's see whether we can show uniqueness using what you have so far.

Suppose there were two such cyclic shifts, one starting with $x_k$ and the other with $x_{\ell}$, where $1 \leqslant k < \ell \leqslant n+1$. Clearly we must have $x_k > 0$ and $x_{\ell} > 0$. This implies $n \geqslant 2$, for if $n = 1$ then exactly one of $x_1,x_2$ is strictly positive. So we must have $\ell > k+1$ or $\ell \leqslant n$ (possibly both). If $\ell > k+1$, we consider the sequence

$$y_i = \begin{cases} x_i &\text{ if } 1 \leqslant i < k \\ x_k + x_{k+1} &\text{ if } i = k \\ x_{i+1} &\text{ if } k < i \leqslant n \end{cases}$$

of length $n$. We note that then

$$\sum_{\rho = 0}^{r} y_{k+\rho} = x_k + \sum_{\rho = 0}^{r} x_{k + 1 + \rho} > 0$$

for all $0 \leqslant r < n$ (where the indices are interpreted modulo $n$ for $y_{k+\rho}$ and modulo $n+1$ for $x_{k+1+\rho}$), and also

$$\sum_{\rho = 0}^r y_{\ell-1+\rho} > 0$$

for $0 \leqslant r < n$. For $\ell - 1 + r < n+k$ we have

$$\sum_{\rho = 0}^r y_{\ell-1+\rho} = \sum_{\rho = 0}^{r} x_{\ell + \rho} > 0$$

and for $\ell - 1 + r \geqslant n + k$ we have

$$\sum_{\rho = 0}^r y_{\ell - 1 + \rho} = \sum_{\rho = 0}^{r+1} x_{\ell + \rho} > 0$$

with the same interpretation of the indices as above. Since $k < \ell-1$, this contradicts the uniqueness of the cyclic shift that we assumed for sequences of length $n$ in the induction hypothesis.

If $\ell = k+1$, we consider the sequence obtained by merging $x_{\ell}$ and $x_{\ell+1}$ instead, and obtain a contradiction in the same way.


Well, this works, but it is a bit messy. Let's have a shorter proof. For a sequence $x_1,\dotsc, x_n$ summing to $1$, define

$$S_k = \sum_{i = 1}^k x_i$$

for $0 \leqslant k \leqslant 2n$, interpreting indices modulo $n$. So $S_0 = 0$, $S_1 = x_1$, and $S_{k+n} = S_k + 1$ for $0 \leqslant k \leqslant n$. Then the partial sum of $r$ elements starting with $x_{k+1}$ is $S_{k+r} - S_k$.

Suppose $0 \leqslant k < n$ is such that the cyclic shift starting with $x_{k+1}$ has all partial sums positive. For $1 \leqslant r \leqslant n-k$ that means $S_k < S_{k+r}$, and for $n-k < r \leqslant n$ the condition $S_{k+r} > S_k$ is equivalent (since the $x_i$ are integers and sum to $1$) to $s_{k+r-n} \geqslant S_k$.

So we see that we must have $S_k \leqslant S_{\ell}$ for $0 \leqslant \ell < k$ and $S_k < S_{\ell}$ for $k < \ell \leqslant n$. That is, $k$ must be the last occurrence of $\min \{S_r : 0 \leqslant r < n\}$. This of course exists and is unique.

$\endgroup$
  • $\begingroup$ I will take a look at your proof. Thanks a lot for answer. I have added my solution too. $\endgroup$ – ZFR Nov 17 '17 at 18:58
  • $\begingroup$ Dear, Daniel! Could you help please with my algebra question? math.stackexchange.com/questions/2579812/… $\endgroup$ – ZFR Dec 25 '17 at 16:28
2
$\begingroup$

In the above post I have shown the existence of cyclic shift of the sequence with positive partial sums. Right now I am goint to show that such sequence is unique. However, my proof is not related with the induction proof.

Let's we have sequence $(x_1,x_2,\dots,x_n)$. One of its cyclic shift which has all of its partial sums positive WLOG let be $(x_1,x_2,\dots,x_n)$ and another is $(x_i,x_{i+1},\dots, x_{n+i-1})$ for some $i\in\{2,\dots,n\}$. Then $x_1+\dots +x_{i-1}>0$ i.e. $x_1+\dots +x_{i-1}\geqslant 1$ and also $x_i+\dots+x_n>0$ i.e. $x_i+\dots+x_n\geqslant 1$ then adding these two inequalities $1=x_1+\dots+x_n\geqslant 2$ which is contradiction. Thus we proved the uniqueness.

$\endgroup$
  • $\begingroup$ That's a nice uniqueness proof. Much nicer than what building on your existence proof yielded. $\endgroup$ – Daniel Fischer Nov 18 '17 at 10:47

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.