Problem 22 · 2009 Math Kangaroo
Stretch
Counting & Probability
careful-countingcasework
How many 10-digit numbers are made up solely of the digits 1, 2 and 3 (not necessarily all of them) and have the property that adjacent digits always differ by exactly 1?
Show answer
Answer: C — 64
Show hints
Hint 1 of 2
Adjacent digits differ by 1, so from a 2 you can go to 1 or 3, but from a 1 you must go to 2.
Still stuck? Show hint 2 →
Hint 2 of 2
Build the count digit by digit, tracking how many strings end in each digit.
Show solution
Approach: count step by step with a small transition table
- Because neighbours differ by 1, a 2 must sit next to a 1 or a 3, while a 1 or a 3 must sit next to a 2 — so 2s and (1-or-3)s strictly alternate.
- That fixes which of the 10 positions hold a 2: either all odd positions or all even positions, giving 2 patterns.
- In each pattern the five non-2 slots are independently a 1 or a 3, so \(2^5 = 32\) ways per pattern.
- Total = \(2 \times 32 = 64\), so the answer is 64.
Mark:
· log in to save