16. How many 10-digit numbers are there whose digits are all 1,2 or 3 and in which adjacent digits differ by 1 ?
16. 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 10digit 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.