HMMT 二月 2013 · 冲刺赛 · 第 18 题

英文解析

18. [ 11 ] Define the sequence of positive integers { a } as follows. Let a = 1 , a = 3 , and for each n > 2,
    n 1 2
    let a be the result of expressing a in base n − 1, then reading the resulting numeral in base n ,
    n n − 1
    then adding 2 (in base n ). For example, a = 3 = 11 , so a = 11 + 2 = 6 . Express a in base
    2 10 2 3 3 3 10 2013
    ten.
    Answer: 23097 We claim that for nonnegative integers m and for 0 ≤ n < 3 · 2 , a =mm
    3 · 2 + nm
    (3 · 2 + n )( m + 2) + 2 n . We will prove this by induction; the base case for a = 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 3
    will divide this into two cases:
    • Case 1: n < 3 · 2 − 1. Then, we want to prove that this is true for m and n + 1. In particular,mmwriting a in base 3 · 2 + n results in the digits m + 2 and 2 n . Consequently, reading it inm
    3 · 2 + nm m mbase 3 · 2 + n +1 gives a = 2+(3 · 2 + n +1)( m +2)+2 n = (2 · 2 + n +1)( m +2)+2( n +1),m
    3 · 2 + n +1
    as desired.
    • Case 2: n = 3 · 2 − 1. Then, we want to prove that this is true for m + 1 and 0. Similarlymmto the previous case, we get that a m = a m +1 = 2 + (3 · 2 + n + 1)( m + 2) + 2 n =
    3 · 2 + n +1
    3 · 2
    m +1 m m +1
    2 + (3 · 2 )( m + 2) + 2(3 · 2 − 1) = (3 · 2 + 0)(( m + 1) + 2) + 2(0), as desired.
    In both cases, we have proved our claim.
    Guts Round