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

HMMT February 2013 — Guts Round — Problem 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 , then n n − 1 adding 2 (in base n ). For example, a = 3 = 11 , so a = 11 + 2 = 6 . Express a in base ten. 2 10 2 3 3 3 10 2013

解析

[ 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. m m Answer: 23097 We claim that for nonnegative integers m and for 0 ≤ n < 3 · 2 , a = 3 · 2 + n m (3 · 2 + n )( m + 2) + 2 n . We will prove this by induction; the base case for a = 6 (when m = 0, 3 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: m • Case 1: n < 3 · 2 − 1. Then, we want to prove that this is true for m and n + 1. In particular, m m writing a in base 3 · 2 + n results in the digits m + 2 and 2 n . Consequently, reading it in 3 · 2 + n m m m m base 3 · 2 + n +1 gives a = 2+(3 · 2 + n +1)( m +2)+2 n = (2 · 2 + n +1)( m +2)+2( n +1), 3 · 2 + n +1 as desired. m • Case 2: n = 3 · 2 − 1. Then, we want to prove that this is true for m + 1 and 0. Similarly m to 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