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 "2015 AIME II Problems/Problem 12"
Line 3: Line 3:
 
There are <math>2^{10} = 1024</math> possible 10-letter strings in which each letter is either an A or a B. Find the number of such strings that do not have more than 3 adjacent letters that are identical.
 
There are <math>2^{10} = 1024</math> possible 10-letter strings in which each letter is either an A or a B. Find the number of such strings that do not have more than 3 adjacent letters that are identical.
  
−
==Solution==
+
==Solution 1==
  
 
The solution is a simple recursion:  
 
The solution is a simple recursion:  
Line 28: Line 28:
 
<math>a_{10}=88</math>, <math>b_{10}=162</math>, and <math>c_{10}=298</math>.
 
<math>a_{10}=88</math>, <math>b_{10}=162</math>, and <math>c_{10}=298</math>.
 
Summing the three up we have our solution: <math>88+162+298=548</math>.
 
Summing the three up we have our solution: <math>88+162+298=548</math>.
 +
 +
==Solution 2==
 +
 +
This is a recursion problem. Let <math>a_n</math> be the number of valid strings of <math>n</math> letters, where the first letter is <math>A</math>.  Similarly, let <math>b_n</math> be the number of valid strings of <math>n</math> letters, where the first letter is <math>B</math>.
 +
 +
Note that <math>a_n=b_{n-1}+b_{n-2}+b_{n-3}</math> for all <math>n\ge4</math>.
 +
 +
Similarly, we have <math>b_n=a_{n-1}+a_{n-2}+a_{n-3}</math> for all <math>n\ge4</math>.
 +
 +
Here is why:  every valid strings of <math>n</math> letters <math>(n\ge4)</math> where the first letter is <math>A</math> must begin with one of the following:
 +
 +
<math>AAAB</math> - and the number of valid ways is <math>b_{n-3}</math>.
 +
 +
<math>AAB</math> - and the number of valid ways is <math>b_{n-2}</math>.
 +
 +
<math>AB</math> - and there are <math>b_{n-1}</math> ways.
 +
 +
We know that <math>a_1=1</math>, <math>a_2=2</math>, and <math>a_3=4</math>.  Similarly, we have <math>b_1=1</math>, <math>b_2=2</math>, and <math>b_3=4</math>.  We can quickly check our recursion to see if our recursive formula works.  By the formula, <math>a_4=b_3+b_2+b_1=7</math>, and listing out all <math>a_4</math>, we can quickly verify our formula.
 +
 +
Therefore, we have the following:
 +
 +
<math>\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c}Value of n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\\hline a & 1 & 2 & 4 & 7 & 13 & 24 & 44 & 81 & 149 & 274\\b & 1 & 2 & 4 & 7 & 13 & 24 & 44 & 81 & 149 & 274\end{tabular}</math>
 +
 +
The total number of valid <math>10</math> letter strings is equal to <math>a_{10}+b_{10}=274+274=\boxed{548}</math>.
  
 
==See also==
 
==See also==
 
{{AIME box|year=2015|n=II|num-b=11|num-a=13}}
 
{{AIME box|year=2015|n=II|num-b=11|num-a=13}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 11:16, 27 March 2015

Problem

There are $2^{10} = 1024$ possible 10-letter strings in which each letter is either an A or a B. Find the number of such strings that do not have more than 3 adjacent letters that are identical.

Solution 1

The solution is a simple recursion:

We have three cases for the ending of a string: three in a row, two in a row, and a single:

...AAA $(1)$ ...BAA $(2)$ ...BBA $(3)$

For case $(1)$, we could only add a B to the end, making it a case $(3)$. For case $(2)$, we could add an A or a B to the end, making it a case $(1)$ if you add an A, or a case $(3)$ if you add a B. For case $(3)$, we could add an A or a B to the end, making it a case $(2)$ or a case $(3)$.

Let us create three series to represent the number of permutations for each case: $\{a\}$, $\{b\}$, and $\{c\}$ representing case $(1)$, $(2)$, and $(3)$ respectively.

The series have the following relationship:

$a_n=b_{n-1}$ $b_n=c_{n-1}$ $c_n=c_{n-1}+a_{n-1}+b_{n-1}$

For $n=3$: $a_3$ and $b_3$ both equal $2$, $c_3=4$. With some simple math, we have: $a_{10}=88$, $b_{10}=162$, and $c_{10}=298$. Summing the three up we have our solution: $88+162+298=548$.

Solution 2

This is a recursion problem. Let $a_n$ be the number of valid strings of $n$ letters, where the first letter is $A$. Similarly, let $b_n$ be the number of valid strings of $n$ letters, where the first letter is $B$.

Note that $a_n=b_{n-1}+b_{n-2}+b_{n-3}$ for all $n\ge4$.

Similarly, we have $b_n=a_{n-1}+a_{n-2}+a_{n-3}$ for all $n\ge4$.

Here is why: every valid strings of $n$ letters $(n\ge4)$ where the first letter is $A$ must begin with one of the following:

$AAAB$ - and the number of valid ways is $b_{n-3}$.

$AAB$ - and the number of valid ways is $b_{n-2}$.

$AB$ - and there are $b_{n-1}$ ways.

We know that $a_1=1$, $a_2=2$, and $a_3=4$. Similarly, we have $b_1=1$, $b_2=2$, and $b_3=4$. We can quickly check our recursion to see if our recursive formula works. By the formula, $a_4=b_3+b_2+b_1=7$, and listing out all $a_4$, we can quickly verify our formula.

Therefore, we have the following:

$\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c}Value of n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\\hline a & 1 & 2 & 4 & 7 & 13 & 24 & 44 & 81 & 149 & 274\\b & 1 & 2 & 4 & 7 & 13 & 24 & 44 & 81 & 149 & 274\end{tabular}$

The total number of valid $10$ letter strings is equal to $a_{10}+b_{10}=274+274=\boxed{548}$.

See also

2015 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 11 		Followed by
Problem 13
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2015_AIME_II_Problems/Problem_12&oldid=69603"