Posts
Area Man Who Talks a Lot About Teaching Teaches His First Full Day in >10
Years
-
I have taught demo and observational classes regularly since I left
full-time teaching but yesterday was the first time I taught every class
for the day. L...
2 years ago
The answer is 97,038,694,279.
ReplyDeleteLet f(n) be the number of n-digit numbers (with leading zeros allowed) that contain two consecutive nines.
Let n>2 be given, and let S be the set of all n-digit numbers that contain two consecutive nines.
If an n-digit number starts with 99 then it belongs to S, and there are 10^(n-2) such numbers.
The number of elements in S that begin with a single 9 is 9*f(n-2), because there are nine choices for the second digit (0-8) and there are f(n-2) ways to complete the remaining n-2 digits.
The number of elements in S that do not begin with 9 is 9*f(n-1), because there are nine choices for the first digit (0-8) and there are f(n-1) ways to complete the remaining n-1 digits.
Therefore f(n) = 9*f(n-1) + 9*f(n-2) + 10^(n-2). We can use this recurrence to rapidly calculate f(12).
f(1) = 0
f(2) = 1
f(3) = 9*1+0+10 = 19
f(4) = 9*19+9*1+100 = 280
...
f(12) = 97,038,694,279