Competition problem — Number theory

Library / /152 of 264

Number theory Difficulty 5.9 AIME, harder Prove it Romania

Initially, a blackboard has written on it the numbers $11$ and $13$ . Each minute an extra number appears on the blackboard, equaling the sum of two numbers already written on the blackboard. Prove that:

a) the number $86$ can not appear on the blackboard;

b) it is possible for $2015$ to appear on the blackboard at some point.

Solution

a) Each number appearing on the blackboard is of the form $11a + 13b$ , with $a, b \in \mathbb{N}^*$ . If $86$ appears on the board, then there exist $a, b \in \mathbb{N}^*$ such that $86 = 11a + 13b$ , whence $b \le 6$ . Then $13b \in \{13, 26, 39, 52, 65, 78\}$ , therefore $11a = 86 - 13b \in \{73, 60, 47, 34, 21, 8\}$ . Since none of these numbers is divisible by $11$ , $86$ can not be written on the blackboard.

b) $2015 = 11 \cdot 182 + 13$ . The number $2015$ can appear on the blackboard after $182$ minutes, in the following way: $13 + 11 = 24 \xrightarrow{+11} 13 + 2 \cdot 11 = 35 \xrightarrow{+11} 13 + 3 \cdot 11 = 46 \xrightarrow{+11} \dots \xrightarrow{+11} 13 + 182 \cdot 11 = 2015$ .

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.