Small Combinatorical Question - Pigeonhole Principle Related

150 Views Asked by At

Suppose there are $77$ positive integers arranged in a row such that their sum is $140$. I want to show there is a sequence of adjacent integers in the row whose sum is $13$.

My line of thought is to use the Pigeonhole principle somehow. I started by denoting the numbers $a_{1},\ldots,a_{77}$ and defining $S_{k}=\sum_{i=1}^{k}a_{i}$ for $1\leq k\leq77$. Then assume by contradiction there are no $1\leq i<j\leq77$ such that $ S_{j}-S_{i}=13$ and this is pretty much where I'm stuck. I thought maybe it's somehow useful to notice that given $i$ any $i<j$ that meets the criteria belongs to $\left\{ i+1,...,i+12\right\}$ since the numbers are positive so the sums increase at least by $1$ each time.

Help would be appreciated.

1

There are 1 best solutions below

1
On BEST ANSWER

According to your definitions:

$$1\leq S_1 < S_2 < \dots < S_{77}\leq140$$

Add $13$ to each term

$$14\leq S_1 + 13 < S_2 + 13 < \dots < S_{77} + 13\leq153$$

We have a total of $77\cdot2=154$ terms (all $S_i$ and $S_i+13$s)

However they're all within the range between $1$ and $153$.

Thus we have two terms such that their difference is $13$.