221 views
Prove that in any sequence of $105$ integers, there will always be a subsequence of consecutive elements in the sequence, whose sum is divisible by $99$.

edited | 221 views

Proof:

Let the integers be $\mathrm {\color {blue} {x_1, x_2, x_3,\cdots \cdots , x_{105}}}$

Assume the following sums:

$\mathrm {S_1 = x_1}$

$\mathrm {S_2 = x_1 + x_2}$

$\vdots \;\;\;= \;\;\; \vdots$

$\vdots \;\;\;= \;\;\; \vdots$

$\mathrm {S_k = x_1 + x_2+\cdots +x_k}$

Thus, in total we have $\mathrm {S_1, S_2, \cdots S_{105}}$ terms. Also, we know that in Modulo $99$, there can be only $99$ possible remainders.

This proves that there has to be some $\mathbf {i<j}$  where $\mathrm {S_i \equiv S_j (\text{mod} \;99)}$

$\therefore$ $99$ divides $\mathrm {S_j – S_i = x_{i+1} + x_{i+2}+...+x_j}$

by Boss (19.2k points)