Sunday, July 19, 2015

Induction - A sequence of integers whose sum is one

Problem Statement:
Given a sequence of integers \( x_1, x_2, \ldots, x_n \) whose some is one, prove that exactly one of the cyclic shifts
\((x_1, x_2, \ldots, x_{n-1}, x_n)\),    \((x_2, x_3, \ldots, x_n, x_1)\),   . . . ,    \((x_n, x_1, \ldots, x_{n-2}, x_{n-1} )\)
has all its prefix sums positive. (prefix sum: the sum of first k elements)

Solution:
We will proceed with mathematical induction.
For the base case \(n=1\), the only possible sequence is \(1\). Hence it satisfies all the desired properties.



Suppose the statement is true for the case \(n = k\) where \(k \geq 1\). We will prove that it is also true for the case \(n = k+1\), i.e. the sequence \(x_1, x_2, \ldots, x_{k+1}\) has exactly one cyclic shift such that all its prefix sums positive.
Let \(s_i = x_i + x_{i+1}\) for all \(i = 1 \ldots k+1\). It can be easily shown that one of the \(s_i\) is positive.
Claim: Amongst all positive \(s_i\), at least one of the \(x_i\) is positive.
Proof: Suppose otherwise. We assume that there is a sequence of \(x_1, x_2, \ldots, x_{k+1}\) such that for all \(x_i > 0\), we will have \(s_i < 0\). More specifically, this leads to the conclusion that for all positive \(x_i\), \(x_{i+1}\) must be negative. Let \(S = \sum_{j \text{ s. t. }x_j>0 } s_j\). Because each \(s_j < 0\), S is also \(< 0\). All positive \(x_i\) is counted once in S, and the corresponding negative integer \(x_{i+1}\) is also counted once (i.e. no double counting of negative numbers). Hence the remaining numbers in the sequence that are not counted in S are all negative. This means that the sum of the remaining numbers with S will be negative, which contradicts the condition that the sum of all the numbers should be equal to 1. (shown)

Now we choose a number \(x_i > 0\) such that \(x_i + x_{i+1} > 0\). Consider the sequence \((x_1, x_2, \ldots, (x_i + x_{i+1}), x_{i+2}, \ldots, x_{k+1})\). Since there are k numbers in this sequence, by mathematical induction, there exists exactly one cyclic shift such that its prefix sums are all positive. Suppose that cycle starts with index j. Now we rewrite the term \((x_i + x_{i+1})\) in the sequence as \(x_i, x_{i+1}\) and we observe that the cycle still satisfies the property. Hence there exists such a cycle in the \(k+1\) sequence, and furthermore, its starting index j is determined by its \(k\) sequence counterpart, hence it is unique. (shown)