SK 2015 Q16
16. How many 10-digit numbers are there whose digits are all 1, 2 or 3 and in which adjacent digits differ by 1?
Senior Kangaroo 2015, Question 16. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: 64
Since adjacent digits differ by 1, each time the number has a digit that is a 1 or a 3, there is only one choice for the next digit as it must be a 2 whereas each time the number has a digit that is a 2, there are two choices for the next digit, namely 1 or 3. Consider all 10-digit numbers starting in a 1. There is only one choice for the second digit since it must be a 2, then two choices for the third digit, then one for the fourth etc. Altogether there are \(1 \times 2 \times 1 \times 2 \times 1 \times 2 \times 1 \times 2 \times 1 = 16\) such numbers. Similarly there are 16 such numbers starting in 3. However, if we consider numbers starting in 2, there are two choices for the second digit then only one choice for the third then two for the fourth etc. Altogether there are \(2 \times 1 \times 2 \times 1 \times 2 \times 1 \times 2 \times 1 \times 2 = 32\) such numbers. Hence there are \(16 + 16 + 32 = 64\) such numbers with the required property.
Solution © UK Mathematics Trust, from the SK 2015 solutions.