Difference between revisions of "Mock AIME 4 2006-2007 Problems/Problem 5"
m |
|||
| Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
| − | How many 10-digit positive | + | How many 10-[[digit]] [[positive integer]]s have all digits either 1 or 2, and have two consecutive 1's? |
==Solution== | ==Solution== | ||
| + | We take as our universe the set of 10-digit [[integer]]s whose digits are all either 1 or 2, of which there are <math>2^{10}</math>, 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 <math>n</math>-digit number is formed either by gluing "2" on to the end of a good <math>(n - 1)</math>-digit number or by gluing "21" onto the end of a good <math>(n - 2)</math>-digit number. This is a [[bijection]] between the good <math>n</math>-digit numbers and the [[union]] of the good <math>(n-1)</math>- and <math>(n - 2)</math>-digit numbers. Thus, the number of good <math>n</math>-digit numbers is the sum of the number of good <math>(n-1)</math>- and <math>(n - 2)</math>-digit numbers. The resulting recursion is exactly that of the Fibonacci numbers with initial values <math>F_1 = 2</math> and <math>F_2 = 3</math>. | |
| + | Thus, our final answer is <math>2^{10} - F_{10} = 1024 - 144 = 880</math>. | ||
---- | ---- | ||
| Line 11: | Line 13: | ||
*[[Mock AIME 4 2006-2007 Problems/Problem 4| Previous Problem]] | *[[Mock AIME 4 2006-2007 Problems/Problem 4| Previous Problem]] | ||
*[[Mock AIME 4 2006-2007 Problems]] | *[[Mock AIME 4 2006-2007 Problems]] | ||
| + | |||
| + | [[Category:Intermediate Combinatorics Problems]] | ||
Revision as of 14:46, 20 January 2007
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 
.
