105 integers contains a subsequence with sum divisible by 99.

Question

I recently came across a problem which states that $$\\$$

Given any sequence of 105 integers there will always be a subsequence of consecutive elements in the sequence, whose sum is divisible by 99.

$$\\$$Can you help me with this problem?

Answer 1

Suppose the integers are $a_1,a_2, a_3, \ldots ,a_{105}$. Consider the following sums

\begin{align*} s_1 &=a_1\\ s_2&=a_1+a_2\\ \vdots & =\vdots\\ s_k&=a_1+a_2+\dotsb +a_k\\ \end{align*} Thus we have $s_1,s_2, \ldots ,s_{105}$ terms. Modulo $99$ there are only $99$ possible remainders. Thus there must be some $i<j$ such that $s_i \equiv s_j \pmod{99}$. Thus $99$ divides $s_j-s_i=a_{i+1}+a_{i+2} +\dotsb +a_{j}$.

Answer 2

Let the sequence be $\{a_1,a_2,\cdots,a_{105} \}$. Let us consider the partial sums $S_k =\sum\limits_{n=1}^k a_n,\ k= 1,2, \cdots, 105$. If $\exists$ some $1 \leq k \leq 105$ such that $99 \mid S_k$ we are through. If not by pigeonhole principle $\exists$ $1 \leq i < j \leq 105$ such that $S_i \equiv S_j\ (\text {mod}\ 99)$. Then the subsequence $\{a_i , a_{i+1}, \cdots, a_j \}$ of consecutive integers has the required property.