Mixing
Putnam and Beyond (Methods of proof) Problem 20
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Here is the problem as stated in "Putnam and Beyond":
Given a sequence of integers $x_1, x_2,...,x_n$ whose sum is 1, prove that exactly one of the cyclic shifts
$x_1,x_2,..., x_n ; x_2,...,x_n,x_1; ....; x_n,x_1,...,x_n-1$
has all of its partial sums positive.( By a partial sum we mean the sum of the first $k$ terms, $kleq n$.
The proof is expected to be inductive, but ( this being my reason for making this query) I have come up with a different "algorithmic" approach. Below I will state my idea and I would be very grateful if you could tell me where I have gone wrong or missed a step, if that is the case.
We start of with the sequence $x_1,x_2,...,x_n$ and perform shifts according to the following scheme.
Our first step will be to group the terms into two sequences $(x_1),(x_2,...,x_n)$. As it is impossible for all terms to be negative or zero, either (i) $x_1 >0$ or (ii) $x_2+...+x_n>0$. If (i) then leave the sequence unchanged and if (ii) perform a single shift to obtain $(x_2,...,x_n),(x_1)$. In the first case we have a sequence with positive partial sums for $k=1$ and $k=n$ and in the second case our sequence has positive partial sums for $k=n-1$ and $k=n$.
We wish to improve on this and continue to group the terms once again as follows for (i) $(x_1,x_2),(x_3,...,x_n)$. Again either (i)' $x_1+x_2>0$ or (ii)' $x_3+...+x_n>0$. In the case of (i)' leave the sequence unchanged and in the case of (ii)' perform one shift to obtain $(x_3,...,x_n), (x_1,x_2)$. Our new sequences now positive partial sums for $k=1,2$ and $k=n$ in case of (i)' and positive partial sums for $k=n-2,n-1$ and $k=n$. Continuing in this manner we can improve the number of positive partial sums by 1 at each iteration.
Now making improvements on the sequence in case (ii), $(x_2,...,x_n),(x_1)$.
We group as we did our original sequence: $(x_2),(x_3,...,x_n,x_1)$. As before we ask whether $(x_2)>0$. If $(x_2)>0$ then leave the sequence unchanged, else perform a single shift to obtain $(x_3,....,x_n,x_1,x_2)$. Either way we have improved on the number of positive partial sums.
Continue in this manner until all partial sums $kleq n$ are positive.
Reading my above argument I am aware that it is very long and very messy, not for the lack of trying. I hope that nevertheless the idea is understood. Thank You for any help!
(P.S. Please do not post the textbook solution, I am aware of it)
proof-verification contest-math
asked 43 mins ago
wittbluenote
888
add a comment |Â
up vote
0
down vote
favorite
Here is the problem as stated in "Putnam and Beyond":
Given a sequence of integers $x_1, x_2,...,x_n$ whose sum is 1, prove that exactly one of the cyclic shifts
$x_1,x_2,..., x_n ; x_2,...,x_n,x_1; ....; x_n,x_1,...,x_n-1$
has all of its partial sums positive.( By a partial sum we mean the sum of the first $k$ terms, $kleq n$.
The proof is expected to be inductive, but ( this being my reason for making this query) I have come up with a different "algorithmic" approach. Below I will state my idea and I would be very grateful if you could tell me where I have gone wrong or missed a step, if that is the case.
We start of with the sequence $x_1,x_2,...,x_n$ and perform shifts according to the following scheme.
Our first step will be to group the terms into two sequences $(x_1),(x_2,...,x_n)$. As it is impossible for all terms to be negative or zero, either (i) $x_1 >0$ or (ii) $x_2+...+x_n>0$. If (i) then leave the sequence unchanged and if (ii) perform a single shift to obtain $(x_2,...,x_n),(x_1)$. In the first case we have a sequence with positive partial sums for $k=1$ and $k=n$ and in the second case our sequence has positive partial sums for $k=n-1$ and $k=n$.
We wish to improve on this and continue to group the terms once again as follows for (i) $(x_1,x_2),(x_3,...,x_n)$. Again either (i)' $x_1+x_2>0$ or (ii)' $x_3+...+x_n>0$. In the case of (i)' leave the sequence unchanged and in the case of (ii)' perform one shift to obtain $(x_3,...,x_n), (x_1,x_2)$. Our new sequences now positive partial sums for $k=1,2$ and $k=n$ in case of (i)' and positive partial sums for $k=n-2,n-1$ and $k=n$. Continuing in this manner we can improve the number of positive partial sums by 1 at each iteration.
Now making improvements on the sequence in case (ii), $(x_2,...,x_n),(x_1)$.
We group as we did our original sequence: $(x_2),(x_3,...,x_n,x_1)$. As before we ask whether $(x_2)>0$. If $(x_2)>0$ then leave the sequence unchanged, else perform a single shift to obtain $(x_3,....,x_n,x_1,x_2)$. Either way we have improved on the number of positive partial sums.
Continue in this manner until all partial sums $kleq n$ are positive.
Reading my above argument I am aware that it is very long and very messy, not for the lack of trying. I hope that nevertheless the idea is understood. Thank You for any help!
(P.S. Please do not post the textbook solution, I am aware of it)
proof-verification contest-math
asked 43 mins ago
wittbluenote
888
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Here is the problem as stated in "Putnam and Beyond":
Given a sequence of integers $x_1, x_2,...,x_n$ whose sum is 1, prove that exactly one of the cyclic shifts
$x_1,x_2,..., x_n ; x_2,...,x_n,x_1; ....; x_n,x_1,...,x_n-1$
has all of its partial sums positive.( By a partial sum we mean the sum of the first $k$ terms, $kleq n$.
The proof is expected to be inductive, but ( this being my reason for making this query) I have come up with a different "algorithmic" approach. Below I will state my idea and I would be very grateful if you could tell me where I have gone wrong or missed a step, if that is the case.
We start of with the sequence $x_1,x_2,...,x_n$ and perform shifts according to the following scheme.
Our first step will be to group the terms into two sequences $(x_1),(x_2,...,x_n)$. As it is impossible for all terms to be negative or zero, either (i) $x_1 >0$ or (ii) $x_2+...+x_n>0$. If (i) then leave the sequence unchanged and if (ii) perform a single shift to obtain $(x_2,...,x_n),(x_1)$. In the first case we have a sequence with positive partial sums for $k=1$ and $k=n$ and in the second case our sequence has positive partial sums for $k=n-1$ and $k=n$.
We wish to improve on this and continue to group the terms once again as follows for (i) $(x_1,x_2),(x_3,...,x_n)$. Again either (i)' $x_1+x_2>0$ or (ii)' $x_3+...+x_n>0$. In the case of (i)' leave the sequence unchanged and in the case of (ii)' perform one shift to obtain $(x_3,...,x_n), (x_1,x_2)$. Our new sequences now positive partial sums for $k=1,2$ and $k=n$ in case of (i)' and positive partial sums for $k=n-2,n-1$ and $k=n$. Continuing in this manner we can improve the number of positive partial sums by 1 at each iteration.
Now making improvements on the sequence in case (ii), $(x_2,...,x_n),(x_1)$.
We group as we did our original sequence: $(x_2),(x_3,...,x_n,x_1)$. As before we ask whether $(x_2)>0$. If $(x_2)>0$ then leave the sequence unchanged, else perform a single shift to obtain $(x_3,....,x_n,x_1,x_2)$. Either way we have improved on the number of positive partial sums.
Continue in this manner until all partial sums $kleq n$ are positive.
Reading my above argument I am aware that it is very long and very messy, not for the lack of trying. I hope that nevertheless the idea is understood. Thank You for any help!
(P.S. Please do not post the textbook solution, I am aware of it)
proof-verification contest-math
asked 43 mins ago
wittbluenote
888
Here is the problem as stated in "Putnam and Beyond":
Given a sequence of integers $x_1, x_2,...,x_n$ whose sum is 1, prove that exactly one of the cyclic shifts
$x_1,x_2,..., x_n ; x_2,...,x_n,x_1; ....; x_n,x_1,...,x_n-1$
has all of its partial sums positive.( By a partial sum we mean the sum of the first $k$ terms, $kleq n$.
The proof is expected to be inductive, but ( this being my reason for making this query) I have come up with a different "algorithmic" approach. Below I will state my idea and I would be very grateful if you could tell me where I have gone wrong or missed a step, if that is the case.
We start of with the sequence $x_1,x_2,...,x_n$ and perform shifts according to the following scheme.
Our first step will be to group the terms into two sequences $(x_1),(x_2,...,x_n)$. As it is impossible for all terms to be negative or zero, either (i) $x_1 >0$ or (ii) $x_2+...+x_n>0$. If (i) then leave the sequence unchanged and if (ii) perform a single shift to obtain $(x_2,...,x_n),(x_1)$. In the first case we have a sequence with positive partial sums for $k=1$ and $k=n$ and in the second case our sequence has positive partial sums for $k=n-1$ and $k=n$.
We wish to improve on this and continue to group the terms once again as follows for (i) $(x_1,x_2),(x_3,...,x_n)$. Again either (i)' $x_1+x_2>0$ or (ii)' $x_3+...+x_n>0$. In the case of (i)' leave the sequence unchanged and in the case of (ii)' perform one shift to obtain $(x_3,...,x_n), (x_1,x_2)$. Our new sequences now positive partial sums for $k=1,2$ and $k=n$ in case of (i)' and positive partial sums for $k=n-2,n-1$ and $k=n$. Continuing in this manner we can improve the number of positive partial sums by 1 at each iteration.
Now making improvements on the sequence in case (ii), $(x_2,...,x_n),(x_1)$.
We group as we did our original sequence: $(x_2),(x_3,...,x_n,x_1)$. As before we ask whether $(x_2)>0$. If $(x_2)>0$ then leave the sequence unchanged, else perform a single shift to obtain $(x_3,....,x_n,x_1,x_2)$. Either way we have improved on the number of positive partial sums.
Continue in this manner until all partial sums $kleq n$ are positive.
Reading my above argument I am aware that it is very long and very messy, not for the lack of trying. I hope that nevertheless the idea is understood. Thank You for any help!
(P.S. Please do not post the textbook solution, I am aware of it)
proof-verification contest-math
asked 43 mins ago
wittbluenote
888
asked 43 mins ago
wittbluenote
888
asked 43 mins ago
wittbluenote
888
asked 43 mins ago
wittbluenote
888
888
add a comment |Â
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873372%2fputnam-and-beyond-methods-of-proof-problem-20%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password