pigeonhole principle with sequence of numbers

Question

Let $(x_1,x_2,x_3,\dots,x_{77})$ be positive numbers. Use the pigeonhole principle to show that, if $\sum_{i=1}^{77}{x_{i}} = 140$, then there exist $j$ and $k$ such that $\sum_{i=j}^{k}{x_{i}} = 13$.

Answer 1

Consider the fact that $\sum\limits_{k=i}^{j}x_{k}=\sum\limits_{k=1}^{j}x_{k}-\sum\limits_{k=1}^{i-1}x_{k}$. In other word, you only need to care about the partial sum $s_{i}=\sum\limits_{k=1}^{i}x_{k}$.

Possible value of all $s_{i}$ and $s_{i}+13$ run from $1$ to $140+13=153$. No 2 partial sum have the same value. Assuming there is no 2 partial sum with a difference of $13$, then every partial sum with value $s_{i}$ will rule out 1 more possible value $s_{i}+13$ in the range from $1$ to $153$. Hence each $s_{i}$ would rule out a total of $2$ value.

There are $77$ possible partial sum. If each of them rule out $2$ possible value among $153$ possible value, then there would be contradiction since $77\times 2=154>153$.