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

HMMT November 2016 — Guts Round — Problem 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 12 2 for any 0 ≤ i ≤ n. Find the number of anti-palindromes less than 3 such that no two consecutive digits in base 3 are equal.

解析

[ 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 12 2 for any 0 ≤ i ≤ n. Find the number of anti-palindromes less than 3 such that no two consecutive 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 half of the number and ensure no pair of consecutive digits are equal. For a number with an even number of digits, the middle pair is 02 or 20 while for a number with an odd number of digits, the middle digit is 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 that n the leading digit is nonzero and the ending digit is 1. Let b be the number ways to do the same such n that 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 gives us a final answer of 126