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?
105 integers contains a subsequence with sum divisible by 99.
combinatoricselementary-number-theorypigeonhole-principlesequences-and-series
Related Question
- Combinatorics – Among $k$ Consecutive Numbers One Has Sum of Digits Divisible by $11$
- Show that in any set of $2n$ integers, there is a subset of $n$ integers whose sum is divisible by $n$.
- Prove that any sequence $a_1,…a_n$, $n \geq 5$ contains a subsequence whose elements properly added or subtracted give a multiple of $n^2$
Best Answer
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}$.