Mock AIME 4 2006-2007 Problems/Problem 5
From AoPSWiki
Contents |
Problem
How many 10-digit positive integers have all digits either 1 or 2, and have two consecutive 1's?
Solution
We take as our universe the set of 10-digit integers whose digits are all either 1 or 2, of which there are 
, and we count the complement. The complement is the set of 10-digit positive integers composed of the digits 1 and 2 with no two consecutive 1s. Counting such numbers is a popular combinatorial problem: we approach it via a recursion.
There are two "good" one-digit numbers (1 and 2) and three good two-digit numbers (12, 21 and 22). Each such 
-digit number is formed either by gluing "2" on to the end of a good 
-digit number or by gluing "21" onto the end of a good 
-digit number. This is a bijection between the good -digit numbers and the union of the good - and -digit numbers. Thus, the number of good -digit numbers is the sum of the number of good - and -digit numbers. The resulting recursion is exactly that of the Fibonacci numbers with initial values 
and 
.
Thus, our final answer is 
.
Solution2
Again, we seek the amount without two consecutive 1s. Assume there are n 2s in one of the numbers. We have to insert the 10-n 1s in the n+1 slots surrounding the 2s. Thus, there are 
possibilities for a number with n 2s. The answer is thus 
.
See also
| Mock AIME 4 2006-2007 (Problems, Source) | ||
| Preceded by Problem 4 | Followed by Problem 6 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
