2024 AMC 10A Problem 10

Consider the following operation. Given a positive integer

n,

n

is a multiple of

3,

then you replace

n

\tfrac{n}{3}.

n

is not a multiple of

3,

then you replace

n

n + 10.

Then continue this process. For example, beginning with

n = 4,

this procedure gives

4 \to 14 \to 24 \to 8

\to 18 \to 6 \to 2 \to 12 \to \cdots.

Suppose you start with

n = 100.

What value results if you perform this operation exactly

100

times?

Show solution

Solution

Just run it from

100:

100 \to 110 \to 120 \to 40

\to 50 \to 60 \to 20

\to 30 \to 10 \to 20

\to 30 \to 10 \to \cdots.

After the

8

th step we’re at

10,

and from there it cycles

10, 20, 30

with period

3.

So step

8 + k

is the

k

th entry of the cycle. For step

100,

k = 92,

and

92 \equiv 2 \pmod 3,

which lands on

30.

Therefore, the answer is C.

Tagged: recursion · modular arithmetic · process simulation · pattern recognition