A $10$-digit number is called a $\textit{cute}$ number if its digits belong to the set $\{1,2,3\}$ and the difference of every pair of consecutive digits is $1$. a) Find the total number of cute numbers. b) Prove that the sum of all cute numbers is divisibel by $1408$.
Problem
Source: IMOTC 2015 Practice Test 1 Problem 2
Tags: combinatorics
28.08.2015 06:03
Note that a cute number is either of the form $ 2X2X2X2X2X $ or of the form $X2X2X2X2X2 $, where $X $ is either $1$ or $3$. In fact, all such numbers are cute. So we have $2^5 + 2^5 = 64$ cute numbers in all . Now, for every cute number $ Y$, there exists a "conjugate" cute number $Z $ formed by replacing the $3's $ in $Y $ by $1's $, and the $1's $ by $ 3's $. Pair the two numbers. It is easy to see (and prove) that the $64$ cute numbers form $32 $ pairs, each cute number being used precisely once. Also two numbers of any pair add to give $4444444444$. So the sum of all cute numbers is $4444444444*32 = 1408*101010101 $, which is a multiple of $1408$.
08.09.2017 19:57
a) Easy to create a recurrence and check $T_n = 2T_{n-2}$ where $ T_n$ is the number of number of $n-digit$ $cute$ numbers. Thus $T_{10} = 64$ using the fact $T_2=4$. (Lol,This was pretty easy just by straight counting ) b)Same idea as in #2 (Also found in an AIME problem) Map every $cute$ number to its image Formed by Interchanging $1$ with $3$ and vice versa and keeping the $2's$ same.One can check the Image itself is also a $cute$ number. Thus we get such $32$ pairs each having sum $4444444444$. Thus one can easily see $4444444444 *32 $ is a multiple of $1408$.
09.12.2022 15:00
Note that you are not required to solve for $n$ being odd, I have just added it as they could have asked it in the paper.