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 "2003 AIME II Problems/Problem 3"
(→‎Solution 3 (Recursion))
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
Define a <math>good~word</math> as a sequence of letters that consists only of the letters <math>A</math>, <math>B</math>, and <math>C</math> - some of these letters may not appear in the sequence - and in which <math>A</math> is never immediately followed by <math>B</math>, <math>B</math> is never immediately followed by <math>C</math>, and <math>C</math> is never immediately followed by <math>A</math>. How many seven-letter good words are there?
+
Define a <math>\text{good~word}</math> as a sequence of letters that consists only of the letters <math>A</math>, <math>B</math>, and <math>C</math> - some of these letters may not appear in the sequence - and in which <math>A</math> is never immediately followed by <math>B</math>, <math>B</math> is never immediately followed by <math>C</math>, and <math>C</math> is never immediately followed by <math>A</math>. How many seven-letter good words are there?
  
 
== Solution 1 ==  
 
== Solution 1 ==  
Line 14: Line 14:
 
== Solution 3 (Recursion) ==
 
== Solution 3 (Recursion) ==
  
−
We solve this problem using recursion. Let f(x) be the number of x-letter good words. Thus f(1) = 3 (A, B or C) and the answer is just f(7).  The recurrence relation can be found by considering the last letter of one of the valid strings of length x - 1.  There are 2 possibilities for the next letter and thus f(x) = 2 * f(x-1).  Now we can find a closed form as f(x) = 3 * 2 ^ (x - 1) (easy to prove by induction) and thus f(7) = 64 * 3 = <math>\boxed{192}</math> seven-letter good words.  ~AK2006
+
We solve this problem using recursion. Let <math>f(x)</math> be the number of <math>x</math>-letter good words. Thus <math>f(1) = 3</math> (A, B or C) and the answer is just <math>f(7)</math>.  The recurrence relation can be found by considering the last letter of one of the valid strings of length <math>x - 1</math>.  There are <math>2</math> possibilities for the next letter and thus <math>f(x) = 2 \cdot f(x-1)</math>.  Now we can find a closed form as <math>f(x) = 3 \cdot 2 ^{x-1}</math> (easy to prove by induction) and thus <math>f(7) = 64 * 3 = \boxed{192}</math> seven-letter good words.  ~AK2006
 +
 
 +
== Video Solution by Sal Khan ==
 +
https://www.youtube.com/watch?v=JU67TL2L1CA&list=PLSQl0a2vh4HCtW1EiNlfW_YoNAA38D0l4&index=9
 +
- AMBRIGGS
  
 
== See also ==
 
== See also ==

Latest revision as of 16:29, 30 July 2022

Problem

Define a $\text{good~word}$ as a sequence of letters that consists only of the letters $A$, $B$, and $C$ - some of these letters may not appear in the sequence - and in which $A$ is never immediately followed by $B$, $B$ is never immediately followed by $C$, and $C$ is never immediately followed by $A$. How many seven-letter good words are there?

Solution 1

There are three letters to make the first letter in the sequence. However, after the first letter (whatever it is), only two letters can follow it, since one of the letters is restricted. Therefore, the number of seven-letter good words is $3*2^6=192$

Therefore, there are $\boxed{192}$ seven-letter good words.

Solution 2

There are three choices for the first letter and two choices for each subsequent letter, so there are $3\cdot2^{n-1}\ n$-letter good words. Substitute $n=7$ to find there are $3\cdot2^6=\boxed{192}$ seven-letter good words. ~ aopsav (Credit to AoPS Alcumus)

Solution 3 (Recursion)

We solve this problem using recursion. Let $f(x)$ be the number of $x$-letter good words. Thus $f(1) = 3$ (A, B or C) and the answer is just $f(7)$. The recurrence relation can be found by considering the last letter of one of the valid strings of length $x - 1$. There are $2$ possibilities for the next letter and thus $f(x) = 2 \cdot f(x-1)$. Now we can find a closed form as $f(x) = 3 \cdot 2 ^{x-1}$ (easy to prove by induction) and thus $f(7) = 64 * 3 = \boxed{192}$ seven-letter good words. ~AK2006

Video Solution by Sal Khan

https://www.youtube.com/watch?v=JU67TL2L1CA&list=PLSQl0a2vh4HCtW1EiNlfW_YoNAA38D0l4&index=9 - AMBRIGGS

See also

2003 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
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=2003_AIME_II_Problems/Problem_3&oldid=176422"