Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mock AIME 4 2006-2007 Problems/Problem 5"

m (box)
(→‎Solution)
 
Line 7: Line 7:
  
 
Thus, our final answer is <math>2^{10} - F_{10} = 1024 - 144 = 880</math>.
 
Thus, our final answer is <math>2^{10} - F_{10} = 1024 - 144 = 880</math>.
 +
 +
==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 <math>{{n+1} \choose{10-n}}</math> possibilities for a number with n 2s. The answer is thus <math>2^{10}- {6 \choose 5} - {7 \choose 4} - {8 \choose 3} - {9 \choose 2} - {10 \choose 1} - {11 \choose 0}=880</math>.
  
 
== See also ==
 
== See also ==

Latest revision as of 13:50, 16 February 2009

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 $2^{10}$, 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 $n$-digit number is formed either by gluing "2" on to the end of a good $(n - 1)$-digit number or by gluing "21" onto the end of a good $(n - 2)$-digit number. This is a bijection between the good $n$-digit numbers and the union of the good $(n-1)$- and $(n - 2)$-digit numbers. Thus, the number of good $n$-digit numbers is the sum of the number of good $(n-1)$- and $(n - 2)$-digit numbers. The resulting recursion is exactly that of the Fibonacci numbers with initial values $F_1 = 2$ and $F_2 = 3$.

Thus, our final answer is $2^{10} - F_{10} = 1024 - 144 = 880$.

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 ${{n+1} \choose{10-n}}$ possibilities for a number with n 2s. The answer is thus $2^{10}- {6 \choose 5} - {7 \choose 4} - {8 \choose 3} - {9 \choose 2} - {10 \choose 1} - {11 \choose 0}=880$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_4_2006-2007_Problems/Problem_5&oldid=30332"