Problem 22 · 2009 Math Kangaroo
Hard
Counting & Probability
casework
How many 10-digit numbers are there which use only the digits 1, 2 and 3 (not necessarily all) and are written in such a way that consecutive digits always have a difference of 1?
Show answer
Answer: C — 64
Show hints
Hint 1 of 2
From a 2 you may go to 1 or 3, but a 1 must be followed by 2 (and a 3 by 2).
Still stuck? Show hint 2 →
Hint 2 of 2
Count step by step how many valid strings of each length end in 1, 2 or 3.
Show solution
Approach: count by tracking the last digit
- Track how many valid strings end in 1, 2, 3 as length grows: a 1 or 3 forces a following 2, while a 2 allows a 1 or 3.
- Iterating this for 10 digits totals 64 strings.
- So there are 64 such numbers.
Mark:
· log in to save