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
biomathematics
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$.
phymaths
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$.
Pyramix
09.12.2022 15:00
Let $t_n$ be the total number of cute numbers with $n$ digits.
Let $a_n,b_n,c_n$ denote all cute numbers ending with $1, 2, 3$, respectively. So, $t_n=a_n+b_n+c_n$.
Case 1) Number ends with $1$/$3$.
Second last number must be $2$ in either case. This means $a_n=b_{n-1}=c_n=b_{n-1}$.
Case 2) Number ends with $2$.
Second last number may be $1$ or $3$. This means $b_n=a_{n-1}+c_{n-1}=2a_{n-1}=2b_{n-2}$.
Also, $t_n=a_n+b_n+c_n=b_n+2b_{n-1}\ \ (\star)$.
Note that $b_1=1$ (number: $2$) and $b_2=2$ (numbers: $12,32$). This gives $b_n=2^{\lfloor\frac{n}{2}\rfloor}$.
Substituting in $(\star)$, we get
$t_{2k}=2^k+2(2^{k-1})=2^{k+1}$,
$t_{2k+1}=2^k+2(2^k)=3\cdot 2^k$.
So, $t_{10}=2^{5+1}=2^6=\boxed{64}$.
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.