2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Nice and simple, thanks :) $\endgroup$
    – Serpahimz
    Jan 7, 2014 at 17:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .