HMMT 十一月 2016 · 冲刺赛 · 第 31 题

英文解析

31. [ 17 ] Define a number to be an anti-palindrome if, when written in base 3 as a a ...a , then a + a =
    n n − 1 0 i n − i
    2 for any 0 ≤ i ≤ n. Find the number of anti-palindromes less than 3 such that no two consecutive 12
    digits in base 3 are equal.
    Proposed by: Shyam Narayanan
    Answer: 126
    Note once the middle digit/pair of digits is determined, it suffices to choose the digits in the left halfof the number and ensure no pair of consecutive digits are equal. For a number with an even numberof digits, the middle pair is 02 or 20 while for a number with an odd number of digits, the middle digitis 1. We can now count recursively.
    Let a be the number of ways to choose n digits no two of which are consecutive and equal such thatnthe leading digit is nonzero and the ending digit is 1. Let b be the number ways to do the same suchnthat the ending digit is 0 or 2.
    Note a = b . Also b = b + 2 a .
    n n − 1 n n − 1 n − 1
    Solving for the terms of the sequence, they are a = 1 , a = b = 1 , a = b = 3 , a = b = 5 , a = b =
    1 2 1 3 2 4 3 5 4
    11 , a = b = 21 , b = 43. Therefore, there are 43 twelve-digit numbers satisfying the condition, 21
    6 5 6
    eleven-digit numbers, 21 ten-digit numbers.... and 1 one-digit number. The sum of these values givesus a final answer of 126