HMMT, 2013

Algebra Difficulty 5.2 AIME, harder Find the answer United States

Problem:

Define the sequence of positive integers $\{a_n\}$ as follows. Let $a_1=1$ , $a_2=3$ , and for each $n>2$ , let $a_n$ be the result of expressing $a_{n-1}$ in base $n-1$ , then reading the resulting numeral in base $n$ , then adding $2$ (in base $n$ ). For example, $a_2=3_{10}=11_2$ , so $a_3=11_3+2_3=6_{10}$ . Express $a_{2013}$ in base ten.

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Answer: 23097

We claim that for nonnegative integers $m$ and for $0 \leq n < 3 \cdot 2^m$ , $a_{3 \cdot 2^m + n} = (3 \cdot 2^m + n)(m+2) + 2n$ . We will prove this by induction; the base case for $a_3 = 6$ (when $m=0$ , $n=0$ ) is given in the problem statement.

Now, suppose that this is true for some pair $m$ and $n$ . We will divide this into two cases:

- Case 1: $n < 3 \cdot 2^m - 1$ . Then, we want to prove that this is true for $m$ and $n+1$ . In particular, writing $a_{3 \cdot 2^m + n}$ in base $3 \cdot 2^m + n$ results in the digits $m+2$ and $2n$ . Consequently, reading it in base $3 \cdot 2^m + n + 1$ gives $a_{3 \cdot 2^m + n + 1} = 2 + (3 \cdot 2^m + n + 1)(m+2) + 2n = (3 \cdot 2^m + n + 1)(m+2) + 2(n+1)$ , as desired.

- Case 2: $n = 3 \cdot 2^m - 1$ . Then, we want to prove that this is true for $m+1$ and $0$ . Similarly to the previous case, we get that $a_{3 \cdot 2^m + n + 1} = a_{3 \cdot 2^{m+1}} = 2 + (3 \cdot 2^m + n + 1)(m+2) + 2n = 2 + (3 \cdot 2^{m+1})(m+2) + 2(3 \cdot 2^m - 1) = (3 \cdot 2^{m+1} + 0)((m+1)+2) + 2(0)$ , as desired.

In both cases, we have proved our claim.

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

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