HMMT 二月 2011 · ALGCALC 赛 · 第 20 题
HMMT February 2011 — ALGCALC Round — Problem 20
题目详情
- Let { a } and { b } be sequences defined recursively by a = 2; b = 2, and a = a 1 + a + b − b ; n n 0 0 n +1 n n n n √ 2 2 b = b 1 + a + b + a . Find the ternary (base 3) representation of a and b . n +1 n n 4 4 n n
解析
- Let { a } and { b } be sequences defined recursively by a = 2; b = 2, and a = a 1 + a + b − b ; n n 0 0 n +1 n n n n √ 2 2 b = b 1 + a + b + a . Find the ternary (base 3) representation of a and b . n +1 n n 4 4 n n Answer: 1000001100111222 and 2211100110000012 √ n 2 2 2 Note first that 1 + a + b = 3 . The proof is by induction; the base case follows trivially from what n n √ 2 2 2 2 2 2 2 2 is given. For the inductive step, note that 1+ a + b = 1+ a (1+ a + b )+ b − 2 a b 1 + a + b + n n n +1 n +1 n n n n n n √ 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 b (1 + a + b ) + a + 2 a b 1 + a + b = 1 + ( a + b )(1 + a + b ) + a + b = (1 + a + b ) . n n n n n n n n n n n n n n n n √ n n +1 2 2 2 2 2 Invoking the inductive hypothesis, we see that 1 + a + b = (3 ) = 3 , as desired. n +1 n +1 The quickest way to finish from here is to consider a sequence of complex numbers { z } defined by n n 2 z = a + b i for all nonnegative integers n . It should be clear that z = 2 + 2 i and z = z (3 + i ). n n n 0 n +1 n 0 1 2 3 2 2 2 2 Therefore, z = (2 + 2 i )(3 + i )(3 + i )(3 + i )(3 + i ). This product is difficult to evaluate in 4 Algebra & Calculus Individual Test the decimal number system, but in ternary the calculation is a cinch! To speed things up, we will 1 use balanced ternary , in which the three digits allowed are − 1 , 0 , and 1 rather than 0 , 1 , and 2. Let 0 1 2 3 2 2 2 2 x + yi = (3 + i )(3 + i )(3 + i )(3 + i ), and consider the balanced ternary representation of x and j j y . For all 0 ≤ j ≤ 15, let x denote the digit in the 3 place of x , let y denote the digit in the 3 place j j of y , and let b ( j ) denote the number of ones in the binary representation of j . It should be clear that x = − 1 if b ( j ) ≡ 2 (mod 4), x = 0 if b ( j ) ≡ 1 (mod 2), and x = 1 if b ( j ) ≡ 0 (mod 4). Similarly, j j j y = − 1 if b ( j ) ≡ 1 (mod 4), y = 0 if b ( j ) ≡ 0 (mod 2), and y = 1 if b ( j ) ≡ 3 (mod 4). Converting j j j to ordinary ternary representation, we see that x = 221211221122001 and y = 110022202212120 . It 3 3 remains to note that a = 2 x − 2 y and b = 2 x + 2 y and perform the requisite arithmetic to arrive at 4 4 the answer above. 1 http://en.wikipedia.org/wiki/Balanced_ternary Algebra & Calculus Individual Test