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"

m (→‎Nonrecursion Solution 3: Fixed formatting)
m (→‎Nonrecursion Solution 3: Oops- last fix was bad)
Line 61: Line 61:
 
We can have from 4 to 10 numbers in our parentheses. For each case, we will start with the largest number possible, usually a bunch of 3s, then go down systematically. Realize also that if we are left with just 2s and 1s, there is only one number of 2s and 1s that adds up to the leftover amount. Our final answer is the sum of all of these parenthetical sets [each set multiplied by its permutations, as order matters] multiplied by two [starting with either A or B, and alternating as we go along].
 
We can have from 4 to 10 numbers in our parentheses. For each case, we will start with the largest number possible, usually a bunch of 3s, then go down systematically. Realize also that if we are left with just 2s and 1s, there is only one number of 2s and 1s that adds up to the leftover amount. Our final answer is the sum of all of these parenthetical sets [each set multiplied by its permutations, as order matters] multiplied by two [starting with either A or B, and alternating as we go along].
  
−
<math>4 \rightarrow (3,3,3,1) = 4, (3,3,2,2) = 6
+
<math>4 \rightarrow (3,3,3,1) = 4, (3,3,2,2) = 6</math>
−
5 \rightarrow (3, 3, 2, 1, 1) = 30, (3, 2, 2, 2, 1) = 20, (2,2,2,2,2)=1
+
<math>5 \rightarrow (3, 3, 2, 1, 1) = 30, (3, 2, 2, 2, 1) = 20, (2,2,2,2,2)=1</math>
−
6 \rightarrow (3,3,1,1,1,1) = 15, (3,2,2,1,1,1) = 60, (2,2,2,2,1,1) = 15
+
<math>6 \rightarrow (3,3,1,1,1,1) = 15, (3,2,2,1,1,1) = 60, (2,2,2,2,1,1) = 15</math>
−
7 \rightarrow (3,2,1,1,1,1,1) = 42, (2,2,2,1,1,1,1) = 35
+
<math>7 \rightarrow (3,2,1,1,1,1,1) = 42, (2,2,2,1,1,1,1) = 35</math>
−
8 \rightarrow (3,1...1) = 8, (2,2,1...1) = 28
+
<math>8 \rightarrow (3,1...1) = 8, (2,2,1...1) = 28</math>
−
9 \rightarrow (2,1...1) = 9
+
<math>9 \rightarrow (2,1...1) = 9</math>
−
10 \rightarrow (1,1....1) =1.</math>
+
<math>10 \rightarrow (1,1....1) =1</math>
  
 
Adding them all up gives you 274; multiplying by 2 gives <math>\boxed{548}</math>.
 
Adding them all up gives you 274; multiplying by 2 gives <math>\boxed{548}</math>.

Revision as of 10:01, 29 August 2017

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=\boxed{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}$.

Notice that $a_n = b_n$, since $a_1=b_1$, $a_2=b_2$, and $a_3=b_3$. Therefore, we didn't really need to list out both recursion formulas, which could save us some time.

Nonrecursion Solution 3

Playing around with strings gives this approach: We have a certain number of As, then Bs, and so on. Therefore, what if we denoted each solution with numbers like $(3,3,3,1)$ to denote AAABBBAAAB or vice versa (starting with Bs)? Every string can be represented like this!

We can have from 4 to 10 numbers in our parentheses. For each case, we will start with the largest number possible, usually a bunch of 3s, then go down systematically. Realize also that if we are left with just 2s and 1s, there is only one number of 2s and 1s that adds up to the leftover amount. Our final answer is the sum of all of these parenthetical sets [each set multiplied by its permutations, as order matters] multiplied by two [starting with either A or B, and alternating as we go along].

$4 \rightarrow (3,3,3,1) = 4, (3,3,2,2) = 6$ $5 \rightarrow (3, 3, 2, 1, 1) = 30, (3, 2, 2, 2, 1) = 20, (2,2,2,2,2)=1$ $6 \rightarrow (3,3,1,1,1,1) = 15, (3,2,2,1,1,1) = 60, (2,2,2,2,1,1) = 15$ $7 \rightarrow (3,2,1,1,1,1,1) = 42, (2,2,2,1,1,1,1) = 35$ $8 \rightarrow (3,1...1) = 8, (2,2,1...1) = 28$ $9 \rightarrow (2,1...1) = 9$ $10 \rightarrow (1,1....1) =1$

Adding them all up gives you 274; multiplying by 2 gives $\boxed{548}$.

Note

This problem has the same general approach as #22 on the 2015 AMC 12A.

In fact, if recursion was your method (solutions 1 and 2), you probably solved problem 8 of THIS AIME with recursion as well!

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=87259"