Problem 23 · 2009 Math Kangaroo
Stretch
Counting & Probability
careful-countingcasework
How many 10-digit numbers exist that are made up solely of the digits 1, 2 and 3 and where adjacent digits always differ by exactly 1?
Show answer
Answer: C — 64
Show hints
Hint 1 of 2
The digit can only step up or down by 1, so 2 must sit between a 1 and a 3.
Still stuck? Show hint 2 →
Hint 2 of 2
Set up how many choices you have at each step and watch the count double.
Show solution
Approach: count step-by-step paths on 1–2–3
- From a 2 you may go to 1 or 3 (two choices); from a 1 or 3 you must go to 2 (one choice).
- Building the 10-digit string, the number of valid continuations doubles every two steps.
- Counting all such strings gives 64.
Mark:
· log in to save