Competition problem — Combinatorics

Library / /17 of 26

Combinatorics Difficulty 4.6 AIME Find the answer United States

Consider the following operation. Given a positive integer $n$ , if $n$ is a multiple of $3$ , then you replace $n$ by $\frac{n}{3}$ . If $n$ is not a multiple of $3$ , then you replace $n$ by $n+10$ . Then continue this process. For example, beginning with $n=4$ , this procedure gives $4 \rightarrow 14 \rightarrow 24 \rightarrow 8 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 12 \rightarrow \dots$ . Suppose you start with $n=100$ . What value results if you perform this operation exactly $100$ times?

Pick one

Solution

Answer (C): The first several iterations give
$100 \rightarrow 110 \rightarrow 120 \rightarrow 40 \rightarrow 50 \rightarrow 60 \rightarrow 20 \rightarrow 30 \rightarrow 10 \rightarrow 20 \rightarrow 30 \rightarrow 10 \rightarrow \dots$
The values will then continue to cycle through $20 \rightarrow 30 \rightarrow 10$ . Note that the value $20$ occurs after $6, 9, 12, 15, \dots$ operations; the value $30$ occurs after $7, 10, 13, 16, \dots$ operations; and the value $10$ occurs after $8, 11, 14, 17, \dots$ operations. Because $100$ has remainder $1$ when divided by $3$ , the value after $100$ operations is $30$ .

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.