Combinatorics problem (Pigeonhole principle).

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