I tried to understand the solution from the book for this question, but I am having hard time to understand it.
How do we know that there exist two terms $x_{j}$ and $x_{j+1}$ such that $x_{j}\gt0$,$x_{j+1}\le0$ by taking indices modulo $k+1$?
Asked
Active
Viewed 33 times
0
-
do examples. What happens, exactly, when $n=2?$ – Will Jagy Mar 07 '24 at 17:13
-
@WillJagy When $n=2$, $x_{1}$ must be positive because all partial sums must be positive. But the sum of $x_{1}$ and $x_{2}$ must be $1$, so $x_{2}$ must be less than or equal to $0$. To be specific, $x_{2}$ is $0$ when $x_{1}$ is $1$, and $x_{2}$ is negative when $x_{1}$ is larger than $1$. – Chanhyuk Park Mar 07 '24 at 17:36
-
@WillJagy I understand it works for $n=2$ case, but I’m not sure how to generalize it to $n=k+1$ case. – Chanhyuk Park Mar 07 '24 at 17:39
-
1You say you don't see the way they are arguing induction. So, now show the $n=3$ case by induction, your own way. I am trying to get across the idea that understanding may not happen all at once, while working on sub-problems should help one understand. Anyway, try $n=3$ – Will Jagy Mar 07 '24 at 17:46
-
Given that you tagged this with contest-math, are you familiar with the "cars around the racetrack with enough fuel to complete a lap" problem? If yes, this is very similar to it, and ideas there should translate over. $\quad$ For an alternative approach, plot $(1, x_1), (2, x_1+x_2), \ldots, (n, x_1 + x_2 + \ldots + x_n)$. Find the minimum of these points. If there are multiple minima, then take the rightmost point. Claim: This is the unique index for which all of the partial sums are positive. Proof: (Obvious) From definition of minima and rightmost. – Calvin Lin Mar 16 '24 at 21:44