Maths Olympiad Prep

Library / /251 of 348

Combinatorics Difficulty 5.0 AIME, harder Find the answer

Define a number to be an anti-palindrome if, when written in base 3 as anan1a0a_{n} a_{n-1} \ldots a_{0}, then ai+ani=2a_{i}+a_{n-i}=2 for any 0in0 \leq i \leq n. Find the number of anti-palindromes less than 3123^{12} such that no two consecutive digits in base 3 are equal.

A number or a short expression. Spacing and $ signs are ignored.

Solution

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 ana_{n} be the number of ways to choose nn digits no two of which are consecutive and equal such that the leading digit is nonzero and the ending digit is 1. Let bnb_{n} be the number ways to do the same such that the ending digit is 0 or 2. Note an=bn1a_{n}=b_{n-1}. Also bn=bn1+2an1b_{n}=b_{n-1}+2 a_{n-1}. Solving for the terms of the sequence, they are a1=1,a2=b1=1,a3=b2=3,a4=b3=5,a5=b4=11,a6=b5=21,b6=43a_{1}=1, a_{2}=b_{1}=1, a_{3}=b_{2}=3, a_{4}=b_{3}=5, a_{5}=b_{4}=11, a_{6}=b_{5}=21, b_{6}=43. Therefore, there are 43 twelve-digit numbers satisfying the condition, 21 eleven-digit numbers, 21 ten-digit numbers.... and 1 one-digit number. The sum of these values gives us a final answer of 126

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.