The Gateway to Computer Science Excellence
+3 votes
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$.
in Numerical Ability by Veteran (105k points)
edited by | 221 views

1 Answer

0 votes

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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
198,560 comments
105,390 users