Combinatorics problem (Pigeonhole principle).

Question

let {${a_i}$} $1\le i \le 55$ be a sequence of positive integers (not 0), and $\sum_{i=1}^{55}a_i \lt 95$.

And i'm asked to prove that there must exist a sequence $k \lt l$ in $[55]$ , such that $\sum_{i=k+1}^{l}a_i = 15$.

i thought about this: if all the sequence is 1's so there, the must exist one, ina case that not all of them 1, all of them cannot be 2, so the sum of the sequence is got to be bounded by 55 and 94, i just feel like it was intended to use the pigeonhole principle and I can't figure out how.

Answer 1

This is essentially the same answer as already given, but from a slightly different point of view. Keep this trick, because it pops up all over the place, for instance in the proof of Chebyshev's Inequality.

Instead of writing $$ S = \sum_{i=1}^{55} a_i $$ where $a_i \in \{1, 2, 3, \cdots\}$, let $N_k$ be the number of $i \in \{1, \cdots, 55\}$ such that $a_i = k$ and write $$ S = \sum_{k=1}^\infty k \cdot N_k. $$ That is, group the $a_i$ by value and add up the totals for each group. Within a group, each element has the same value so you need only count the elements. If you're familiar with measure theory, this is essentially converting a Riemann integral into a Lebesgue integral. (Conversely, if measure theory is confusing, thinking of it like this might help.)

Now observe that for any $a_i > 1$, we are adding at least $2$ to the sum, so we can approximate like this: \begin{align} S &= N_1 + \sum_{k=2}^\infty k \cdot N_k \\ &\ge N_1 + 2 \cdot \sum_{k=2}^\infty N_k \\ &= N_1 + 2 \cdot (55 - N_1) \\ &= 110 - N_1. \end{align}

From here, use the fact that $S < 95$ to show that there are a large number of $a_i$ with $a_i = 1$.

Answer 2

Consider the sequence of initial sums $S(0),S(1),\ldots,S(55)$ $$ S(n)=\sum_{i=1}^na_i. $$ We have $$S(0)=0<S(1)<S(2)<\cdots<S(55)<95,$$ a sequence of 56 distinct integers in the interval $[0,94]$ of $95$ possibilities.

Consider also the sequence of numbers $T(i)=S(i)-15$. There are 56 of those as well, all integers in the range $[-15,79]$. Because they are all distinct, at least $56-15=41$ of them are non-negative.

Hints:

• Can you show that the sets $\{S(i)\mid 0\le i<56\}$ and $\{T(i)\mid 0\le i<56\}$ must have a non-empty intersection?
• Do you see how the claim follows from this?

Spoiler #1

Between them the two sets have 97 positive integers in the range $[0,94]$ so the pigeonhole principle tells us that there is some overlap.

Spoiler #2

If $T(\ell)=S(\ell)-15=S(k)$ then $$ \sum_{i=k+1}^\ell a_i=S(\ell)-S(k)=15.$$