HMMT 二月 2011 · ALGCALC 赛 · 第 20 题

英文解析

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 nn 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
    √
    2 n
    2 2
    Note first that 1 + a + b = 3 . The proof is by induction; the base case follows trivially from whatn 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 nn +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 nn 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 byn
    2 nz = 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
    Algebra & Calculus Individual Test 4
    the decimal number system, but in ternary the calculation is a cinch! To speed things up, we willuse balanced ternary , in which the three digits allowed are − 1 , 0 , and 1 rather than 0 , 1 , and 2. Let 1
    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 andj jy . For all 0 ≤ j ≤ 15, let x denote the digit in the 3 place of x , let y denote the digit in the 3 placej jof y , and let b ( j ) denote the number of ones in the binary representation of j . It should be clear thatx = − 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 jy = − 1 if b ( j ) ≡ 1 (mod 4), y = 0 if b ( j ) ≡ 0 (mod 2), and y = 1 if b ( j ) ≡ 3 (mod 4). Convertingj j jto 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.
    http://en.wikipedia.org/wiki/Balanced_ternary 1
    Algebra & Calculus Individual Test