And here is Le Monde mathematical puzzle last competition problem
Find the number of integers such that their 15 digits are all between 1,2,3,4, and the absolute difference between two consecutive digits is 1. Among these numbers how many have 1 as their three-before-last digit and how many have 2?
Combinatorics!!! While it seems like a Gordian knot because the number of choices depends on whether or not a digit is an endpoint (1 or 4), there is a nice recurrence relation between the numbers of such integers with n digits and leftmost digit i, namely that
n⁴=(n-1)³, n³=(n-1)²+(n-1)⁴, n²=(n-1)²+(n-1)¹, n¹=(n-1)²
with starting values 1¹=1²=1³=1⁴=1 (and hopefully obvious notations). Hence it is sufficient to iterate the corresponding transition matrix
on this starting vector 14 times (with R, which does not enjoy a built-in matrix power) to end up with
15¹=610, 15²= 987, 15³= 987, 15⁴= 610
which leads to 3194 different numbers as the solution to the first question. As pointed out later by Amic and Robin in Dauphine, this happens to be twice Fibonacci’s sequence.
For the second question, the same matrix applies, with a different initial vector. Out of the 3+5+5+3=16 different integers with 4 digits, 3 start with 1 and 5 with 2. Then multiplying (3,0,0,0) by M¹⁰ leads to 267+165=432 different values for the 15 digit integers and multiplying (0,5,0,0) by M¹⁰ to. 445+720=1165 integers. (With the reassuring property that 432+1165 is half of 3194!) This is yet another puzzle in the competition that is of no special difficulty and with no further challenge going from the first to the second question…
Related