Sunday, July 19, 2015

Induction - A sequence of integers whose sum is one

Problem Statement:
Given a sequence of integers x1,x2,,xn whose some is one, prove that exactly one of the cyclic shifts
(x1,x2,,xn1,xn),    (x2,x3,,xn,x1),   . . . ,    (xn,x1,,xn2,xn1)
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 k1. We will prove that it is also true for the case n=k+1, i.e. the sequence x1,x2,,xk+1 has exactly one cyclic shift such that all its prefix sums positive.
Let si=xi+xi+1 for all i=1k+1. It can be easily shown that one of the si is positive.
Claim: Amongst all positive si, at least one of the xi is positive.
Proof: Suppose otherwise. We assume that there is a sequence of x1,x2,,xk+1 such that for all xi>0, we will have si<0. More specifically, this leads to the conclusion that for all positive xi, xi+1 must be negative. Let S=j s. t. xj>0sj. Because each sj<0, S is also <0. All positive xi is counted once in S, and the corresponding negative integer xi+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 xi>0 such that xi+xi+1>0. Consider the sequence (x1,x2,,(xi+xi+1),xi+2,,xk+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 (xi+xi+1) in the sequence as xi,xi+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)

No comments:

Post a Comment