Competition problem — Combinatorics

Library / /1 of 18

Combinatorics Difficulty 2.9 Junior Prove it 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?

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$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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