Track / Stage 2 / 239 of 240 #479 of 2444

Problem 479

Combinatorics Difficulty 2.9 Prove it Junior Macedonian Mathematical Olympiad · North Macedonia

The numbers $1$ , $2$ , $\ldots$ , $2009$ are written on a board. Some of them are erased and the remainder of their sum divided with $13$ is written on the board. After a finite number of repetition of the above procedure only three numbers have left, two of which are $99$ and $999$ . What is the third number?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Let $x$ be the third number. After every procedure the remainder of the sum of the numbers on the board divided with $13$ is unchanged.

$1+2+3+\ldots+2009 = \frac{2009 \cdot 2010}{2} = 1005 \cdot 2009$

divided with $13$ has remainder $2$ .

Hence $99+999+x$ divided with $13$ has remainder $2$ . Now $99+999=1098$ has remainder $6$ and $99$ and $999$ are not remainders, follows that $0 \le x < 13$ i.e. $x=9$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.