Pigeonhole principle - sum of sequence of numbers

Question

Let $a_1,...,a_{55}$ be a sequence of positive integers such that $\sum_{i=1}^{55}a_i < 95$. Show that there are positive integers $1 \leq k<l \leq 55$ such that $\sum_{i=k+1}^{l}a_i = 15$. This should be using Pigeonhole principle but I am not sure how. I tried to use some kind of induction which didn't work, and I also noticed that the number of $1$'s in the sequence is between $16$ and $55$, so I'm pretty sure that this $15$ has something to do with the at least $16$ $1$'s.
Can someone give a solution or a hint?

Answer 1

For each $1\leq i\leq 55$ define $x_i=a_1+a_2+...+a_i$. Since the integers are positive we know that $1\leq x_1<x_2<...<x_{55}\leq 94$. Now look at the following set:

$A=\{x_1,...,x_{55},x_1+15,...,x_{55}+15\}$

The number of elements in $A$ is at most $94+15=109$, because every element is an integer in $\{1,2,...,109\}$. But from the way I defined the set it looks like there are $110$ elements. From the pigeonhole principle we get that there must be a duplicate. Since $x_1,...,x_{55}$ are all different elements, and so are $x_1+15,...,x_{55}+15$ we have to conclude that there are some $i,j$ for which $x_i=x_j+15$. And that gives us $15=x_i-x_j=a_{j+1}+...a_{j+2}+...+a_i$.