AoPS Classes Math Jam
Go back to the Math Jam ArchiveAoPS instructors will discuss the upcoming AIME Problem Series B class. Sample problems from the class will be discussed. See the Online Classes pages for details on the class.
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
Facilitator: Richard Rusczyk
rrusczyk19:31:07
Hello, and welcome to an Art of Problem Solving Math Jam. Today we'll be discussing the AIME Problem Series. We will go through a pair of example problems, and then discuss how the class will work. Since we're only discussing one class tonight, this will be a pretty short Math Jam.
Hello, and welcome to an Art of Problem Solving Math Jam. Today we'll be discussing the AIME Problem Series. We will go through a pair of example problems, and then discuss how the class will work. Since we're only discussing one class tonight, this will be a pretty short Math Jam.
rrusczyk19:31:15
My name is Richard Rusczyk. I founded Art of Problem Solving and have written several Art of Problem Solving textbooks.
My name is Richard Rusczyk. I founded Art of Problem Solving and have written several Art of Problem Solving textbooks.
rrusczyk19:31:20
Before we get started I would like to take a moment to explain our Virtual Classroom to those who have not previously participated in a Math Jam or one of our online classes.
Before we get started I would like to take a moment to explain our Virtual Classroom to those who have not previously participated in a Math Jam or one of our online classes.
rrusczyk19:31:26
The classroom is moderated: students can type into the classroom, but only the moderators can choose a comment to drop into the classroom. So, when you send a message, it will not appear immediately, and may not appear at all. This helps keep the class organized and on track. This also means that only well-written comments will be dropped into the classroom, so please take time writing responses that are complete and easy to read. Also, only moderators can enter into private chats with other people in the classroom.
The classroom is moderated: students can type into the classroom, but only the moderators can choose a comment to drop into the classroom. So, when you send a message, it will not appear immediately, and may not appear at all. This helps keep the class organized and on track. This also means that only well-written comments will be dropped into the classroom, so please take time writing responses that are complete and easy to read. Also, only moderators can enter into private chats with other people in the classroom.
rrusczyk19:32:15
Note that it is not possible for the instructor to personally respond to every comment that you submit -- please do not take it personally if your comment is not posted or responded to! I will try to respond to all questions to the extent that I can. I will let you know when to start asking questions about the classes.
Note that it is not possible for the instructor to personally respond to every comment that you submit -- please do not take it personally if your comment is not posted or responded to! I will try to respond to all questions to the extent that I can. I will let you know when to start asking questions about the classes.
rrusczyk19:32:26
The virtual classroom is LaTeX enabled. LaTeX allows users to make nice equations and other math expressions. If you would like to learn how to write in LaTeX, click on the tab on the left side panel of our site and there is a tutorial and reference guide there.
The virtual classroom is LaTeX enabled. LaTeX allows users to make nice equations and other math expressions. If you would like to learn how to write in LaTeX, click on the tab on the left side panel of our site and there is a tutorial and reference guide there.
rrusczyk19:32:54
You do not need to learn LaTeX to use our classes or our classroom!
You do not need to learn LaTeX to use our classes or our classroom!
rrusczyk19:32:58
Using LaTeX in the virtual classroom is slightly different than using it on the message board or in a LaTeX editor. If anything you type up in a post uses LaTeX, then you must use a semicolon (;) to begin your post. For example, if you type
Using LaTeX in the virtual classroom is slightly different than using it on the message board or in a LaTeX editor. If anything you type up in a post uses LaTeX, then you must use a semicolon (;) to begin your post. For example, if you type
rrusczyk19:33:02
rrusczyk19:33:08
This message will look like this when posted in the classroom:
This message will look like this when posted in the classroom:
rrusczyk19:33:10
rrusczyk19:33:14
Just remember, if your post uses LaTeX, use the semicolon (;) to begin your post!
Just remember, if your post uses LaTeX, use the semicolon (;) to begin your post!
rrusczyk19:33:20
One last thing: we recommend not to use a wireless connection while in the classroom. These have a tendency to cause disconnections. Please use a wired connection if possible.
One last thing: we recommend not to use a wireless connection while in the classroom. These have a tendency to cause disconnections. Please use a wired connection if possible.
rrusczyk19:33:46
Are there any questions about the classroom before we dive into discussing the AIME Problem Series class?
Are there any questions about the classroom before we dive into discussing the AIME Problem Series class?
grn_trtle19:34:30
naw man get started
naw man get started
rrusczyk19:34:34
Good idea :)
Good idea :)
rrusczyk19:34:40
The AIME Problem Series A class starts on December 2, and meets every Tuesday from 7:30-9:00 PM Eastern. The class meets for 12 weeks and ends on March 3. (There are no classes during the winter break.) The course is designed to cover a large portion of the curriculum tested on the AIME exam.
The AIME Problem Series A class starts on December 2, and meets every Tuesday from 7:30-9:00 PM Eastern. The class meets for 12 weeks and ends on March 3. (There are no classes during the winter break.) The course is designed to cover a large portion of the curriculum tested on the AIME exam.
rrusczyk19:34:48
The AIME Problem Series will be taught by Sean Markan. Sean participated in numerous math and science programs in high school, including the Math Olympiad Summer Program in 2001 and the US Physics Team in 2000 and 2002. He also won the Mandelbrot Competition in 2002. He graduated from MIT with a degree in Physics in 2006.
The AIME Problem Series will be taught by Sean Markan. Sean participated in numerous math and science programs in high school, including the Math Olympiad Summer Program in 2001 and the US Physics Team in 2000 and 2002. He also won the Mandelbrot Competition in 2002. He graduated from MIT with a degree in Physics in 2006.
rrusczyk19:34:56
Almost all of the problems in the AIME Problem Series B come from past AIME contests.
Almost all of the problems in the AIME Problem Series B come from past AIME contests.
rrusczyk19:35:12
The following problems are taken directly from the AIME Problem Series.
The following problems are taken directly from the AIME Problem Series.
rrusczyk19:35:16
rrusczyk19:35:20
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/1983aime6k14.gif
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/1983aime6k14.gif
rrusczyk19:35:30
Any suggestions or observations?
Any suggestions or observations?
mz94_219:35:50
6=7-1; 8=7+1?
6=7-1; 8=7+1?
rrusczyk19:35:56
And why might we think of that?
And why might we think of that?
ycz900019:36:14
49 = 7^2
49 = 7^2
rrusczyk19:36:18
crazypianist111619:36:59
(7-1)^n + (7+1)^n
(7-1)^n + (7+1)^n
rrusczyk19:37:18
And then what will we do to analyze these two?
And then what will we do to analyze these two?
jvenezuela71619:37:41
Binomial Theorem.
Binomial Theorem.
ycz900019:37:41
binomial expansion
binomial expansion
rrusczyk19:37:44
rrusczyk19:37:48
rrusczyk19:37:52
mz94_219:38:08
if we apply the binomial theorem to that equation; we get that all teh numbers with a n nCr odd # cancel out
if we apply the binomial theorem to that equation; we get that all teh numbers with a n nCr odd # cancel out
rrusczyk19:38:27
Indeed -- but we still have lots of stuff left. Why do these expansions help us?
Indeed -- but we still have lots of stuff left. Why do these expansions help us?
rrusczyk19:39:12
Keep your eye on the ball! Don't forget the goal in this problem.
Keep your eye on the ball! Don't forget the goal in this problem.
ycz900019:39:41
every term except the last two contain a factor of 7^2
every term except the last two contain a factor of 7^2
jvenezuela71619:39:41
(mod 7^2), all of the terms with exponents greater than 2 will have remainder 0.
(mod 7^2), all of the terms with exponents greater than 2 will have remainder 0.
mz94_219:39:41
everything but 83 ncr 0 and 83 ncr 82 is a multiple of 7^2!
everything but 83 ncr 0 and 83 ncr 82 is a multiple of 7^2!
rrusczyk19:40:00
rrusczyk19:40:14
Mighty convenient! So, what is our answer?
Mighty convenient! So, what is our answer?
jvenezuela71619:41:05
mz94_219:41:05
35
35
ycz900019:41:05
35
35
rrusczyk19:41:08
Our final answer is the remainder when 1162 is divided by 49, which is 35.
Our final answer is the remainder when 1162 is divided by 49, which is 35.
rrusczyk19:41:59
Are there any questions about this problem?
Are there any questions about this problem?
rrusczyk19:42:16
(This problem is on the easy end of the problems we discuss in the AIME Problem Series.)
(This problem is on the easy end of the problems we discuss in the AIME Problem Series.)
jvenezuela71619:42:34
Was this an AIME problem? If so, where on the test?
Was this an AIME problem? If so, where on the test?
vvipul19:42:34
what number was this on the aime it came from?
what number was this on the aime it came from?
rrusczyk19:43:03
I believe this was #6 in 1983. Nowadays, I think this would be in the first 5 problems.
I believe this was #6 in 1983. Nowadays, I think this would be in the first 5 problems.
crazypianist111619:43:05
what are the 3 lines that jvenezuela used?
what are the 3 lines that jvenezuela used?
rrusczyk19:43:40
That's a reference to modular arithmetic. You can read more about that in the AoPSWiki, or in our Introduction to Number Theory text. It's one of the very fundamental building blocks of number theory, so you'll want to learn it.
That's a reference to modular arithmetic. You can read more about that in the AoPSWiki, or in our Introduction to Number Theory text. It's one of the very fundamental building blocks of number theory, so you'll want to learn it.
jvenezuela71619:44:04
They are congruent mod 49; that is they have the same remainder when divided by 49. Pretty much the same thing as rrusczyk said.
They are congruent mod 49; that is they have the same remainder when divided by 49. Pretty much the same thing as rrusczyk said.
rrusczyk19:44:07
For the purposes of this problem, it basically means that 1162 has remainder 35 when divided by 49.
For the purposes of this problem, it basically means that 1162 has remainder 35 when divided by 49.
RedCardinal19:44:09
how did you get 83(7+7)
how did you get 83(7+7)
rrusczyk19:44:14
We did the expansions:
We did the expansions:
rrusczyk19:44:17
rrusczyk19:44:22
rrusczyk19:44:41
Everything on the right side of each of these is divisible by 7^2 except the last two terms of each.
Everything on the right side of each of these is divisible by 7^2 except the last two terms of each.
rrusczyk19:45:01
So, they contribute nothing to the remainder when we add these, and then divide by 49.
So, they contribute nothing to the remainder when we add these, and then divide by 49.
rrusczyk19:45:22
rrusczyk19:45:46
Let's check out the other problem.
Let's check out the other problem.
rrusczyk19:45:49
rrusczyk19:45:54
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/1990aime9NoHH.gif
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/1990aime9NoHH.gif
rrusczyk19:46:16
Where do we start?
Where do we start?
dtl4219:46:33
There are 2^10 total possibilities?
There are 2^10 total possibilities?
rrusczyk19:46:47
rrusczyk19:47:02
Now, we just need to count the number of ways we can have no consecutive heads. . .
Now, we just need to count the number of ways we can have no consecutive heads. . .
rrusczyk19:47:16
Unfortunately, it's not so easy to see how to do that!
Unfortunately, it's not so easy to see how to do that!
rrusczyk19:47:24
What might we do to get a feel for the problem?
What might we do to get a feel for the problem?
spitfire19:47:42
or count the ways to have consecutive heads?
or count the ways to have consecutive heads?
everestshi19:47:42
Or we could count the opposite, the number of ways there are consecutive heads
Or we could count the opposite, the number of ways there are consecutive heads
everestshi19:47:42
try smaller numbers?
try smaller numbers?
jvenezuela71619:47:42
Try smaller cases.
Try smaller cases.
ycz900019:47:42
try smaller examples
try smaller examples
rrusczyk19:48:14
These are both fine strategies. If you try the first, you'll quickly go to the second, since it's not so clear how to count the opposite in this case, either.
These are both fine strategies. If you try the first, you'll quickly go to the second, since it's not so clear how to count the opposite in this case, either.
rrusczyk19:48:31
So, let's try the problem for smaller sequences of tosses and look for a pattern.
So, let's try the problem for smaller sequences of tosses and look for a pattern.
rrusczyk19:48:47
How many ways can we toss one coin without consecutive heads?
How many ways can we toss one coin without consecutive heads?
ycz900019:49:35
2
2
jonathanyim19:49:35
2 ways??
2 ways??
jonathanyim19:49:35
2 ways??
2 ways??
rrusczyk19:49:46
One toss outcomes without HH:
H
T
One toss outcomes without HH:
H
T
rrusczyk19:49:51
Just 2 ways. Not so hard.
Just 2 ways. Not so hard.
rrusczyk19:49:54
How about 2 tosses?
How about 2 tosses?
everestshi19:50:05
it's 3 out of 4 for 2 coins
it's 3 out of 4 for 2 coins
jvenezuela71619:50:05
3 ways: HT, TH, TT
3 ways: HT, TH, TT
AIME_is_hard19:50:05
3
3
mz94_219:50:05
3
3
rrusczyk19:50:08
Two toss outcomes without HH:
HT
TH
TT
Two toss outcomes without HH:
HT
TH
TT
rrusczyk19:50:11
Three ways.
Three ways.
rrusczyk19:50:16
In what ways could we toss a coin three times without ending up with HH in the sequence?
In what ways could we toss a coin three times without ending up with HH in the sequence?
ycz900019:51:01
everything except HHT, THH, HHH; 8-3 = 5
everything except HHT, THH, HHH; 8-3 = 5
dtl4219:51:01
5: HTH, THT, TTH, HTT, TTT
5: HTH, THT, TTH, HTT, TTT
vvipul19:51:01
5 ways: TTT HTH THT TTH HTT
5 ways: TTT HTH THT TTH HTT
grn_trtle19:51:01
HTH THT TTH HTT TTT
HTH THT TTH HTT TTT
rrusczyk19:51:05
Three toss outcomes without HH:
HTH
HTT
THT
TTH
TTT
Three toss outcomes without HH:
HTH
HTT
THT
TTH
TTT
rrusczyk19:51:11
We have 5 ways.
We have 5 ways.
rrusczyk19:51:26
In what ways could we toss a coin four times without ending up with HH in the sequence?
In what ways could we toss a coin four times without ending up with HH in the sequence?
jvenezuela71619:52:42
8: TTTT,TTTH,TTHT,THTT,HTTT,THTH,HTTH,HTHT
8: TTTT,TTTH,TTHT,THTT,HTTT,THTH,HTTH,HTHT
EMetz19:52:42
8
8
RedCardinal19:52:42
8
8
rrusczyk19:52:46
Four toss outcomes without HH:
HTHT
HTTH
HTTT
THTH
THTT
TTHT
TTTH
TTTT
Four toss outcomes without HH:
HTHT
HTTH
HTTT
THTH
THTT
TTHT
TTTH
TTTT
rrusczyk19:52:59
There are 8. Anyone notice anything interesting?
There are 8. Anyone notice anything interesting?
dtl4219:53:10
Maybe 8? Fibbonacci?
Maybe 8? Fibbonacci?
RedCardinal19:53:10
we get the fibonacci sequence
we get the fibonacci sequence
spitfire19:53:10
fibonacci?
fibonacci?
jvenezuela71619:53:10
(2,3,5,8,...) ... 2+3=5, 3+5=8, ... Hmm...
(2,3,5,8,...) ... 2+3=5, 3+5=8, ... Hmm...
AIME_is_hard19:53:13
fibonacci sequence
fibonacci sequence
mz94_219:53:13
fibonnaci #s?
fibonnaci #s?
everestshi19:53:13
fibonacci numbers
fibonacci numbers
grn_trtle19:53:13
FIBONACCIIIIIIII!!!!
FIBONACCIIIIIIII!!!!
rrusczyk19:53:20
It sure looks like Fibonacci!
It sure looks like Fibonacci!
rrusczyk19:53:43
(At this point, you could probably guess the answer on the AIME, but we're not going to let you get away with that here!!)
(At this point, you could probably guess the answer on the AIME, but we're not going to let you get away with that here!!)
rrusczyk19:53:46
After all, it might be a:
After all, it might be a:
jvenezuela71619:53:48
Lucky coincidence.
Lucky coincidence.
rrusczyk19:54:24
We think we are getting Fibonacci numbers as our answer. (These are pretty common in AIME problems.)
We think we are getting Fibonacci numbers as our answer. (These are pretty common in AIME problems.)
rrusczyk19:54:50
As background, the Fibonacci sequence is 1,1,2,3,5,8,13
As background, the Fibonacci sequence is 1,1,2,3,5,8,13
rrusczyk19:54:58
Each term is the sum of the two before it.
Each term is the sum of the two before it.
rrusczyk19:55:22
These are the numbers coming out in our problem, so we now have to prove that we'll keep getting Fibonacci numbers.
These are the numbers coming out in our problem, so we now have to prove that we'll keep getting Fibonacci numbers.
rrusczyk19:55:27
What tool are we likely to use?
What tool are we likely to use?
jvenezuela71619:56:08
Recursion! :D
Recursion! :D
vvipul19:56:08
Recursion
Recursion
rrusczyk19:56:24
We define the Fibonacci numbers with recursion:
We define the Fibonacci numbers with recursion:
rrusczyk19:56:41
F(n) = F(n-1) + F(n-2).
F(n) = F(n-1) + F(n-2).
rrusczyk19:57:06
We let F(0) = 0 and F(1) = 1, and we get F(2) =1, F(3) = 2, F(4) = 3, F(5) = 5, and so on.
We let F(0) = 0 and F(1) = 1, and we get F(2) =1, F(3) = 2, F(4) = 3, F(5) = 5, and so on.
rrusczyk19:57:25
That's how we define the Fibonacci numbers.
That's how we define the Fibonacci numbers.
rrusczyk19:57:33
So, we think we can use recursion in this problem.
So, we think we can use recursion in this problem.
rrusczyk19:58:05
By recursion, I mean, we count the number of allowable sequences for n flips in terms of the number of ways for n-1 flips and for n-2 flips.
By recursion, I mean, we count the number of allowable sequences for n flips in terms of the number of ways for n-1 flips and for n-2 flips.
rrusczyk19:58:41
To get an idea how we'll do that here, let's look at our examples again:
To get an idea how we'll do that here, let's look at our examples again:
rrusczyk19:58:48
Two toss outcomes without HH:
HT
TH
TT
Two toss outcomes without HH:
HT
TH
TT
rrusczyk19:58:50
Three toss outcomes without HH:
HTH
HTT
THT
TTH
TTT
Three toss outcomes without HH:
HTH
HTT
THT
TTH
TTT
rrusczyk19:58:53
Four toss outcomes without HH:
HTHT
HTTH
HTTT
THTH
THTT
TTHT
TTTH
TTTT
Four toss outcomes without HH:
HTHT
HTTH
HTTT
THTH
THTT
TTHT
TTTH
TTTT
rrusczyk19:59:30
Notice anything interesting when you compare the 4-toss outcomes to the 2- and 3-toss outcomes?
Notice anything interesting when you compare the 4-toss outcomes to the 2- and 3-toss outcomes?
everestshi20:00:46
it;s the 2nd and the 3rd added up....
it;s the 2nd and the 3rd added up....
rrusczyk20:00:51
True -- anything else?
True -- anything else?
lokito20:01:03
There are 5 that end in T and 3 that end in H- the previous two fibonaccci numbers
There are 5 that end in T and 3 that end in H- the previous two fibonaccci numbers
vvipul20:01:03
for the ones which end in T, the orderings are in 1:1 correspondence with 3-toss outcomes. For the ones ending in H, they are in 1:1 correspondence with teh 2-toss outcomes
for the ones which end in T, the orderings are in 1:1 correspondence with 3-toss outcomes. For the ones ending in H, they are in 1:1 correspondence with teh 2-toss outcomes
rrusczyk20:01:12
Very interesting observation!
Very interesting observation!
rrusczyk20:01:25
Let's look at those again:
Let's look at those again:
rrusczyk20:01:30
Two toss outcomes without HH:
HT
TH
TT
Two toss outcomes without HH:
HT
TH
TT
rrusczyk20:01:33
Three toss outcomes without HH:
HTH
HTT
THT
TTH
TTT
Three toss outcomes without HH:
HTH
HTT
THT
TTH
TTT
rrusczyk20:01:37
Four toss outcomes without HH:
HTHT
HTTH
HTTT
THTH
THTT
TTHT
TTTH
TTTT
Four toss outcomes without HH:
HTHT
HTTH
HTTT
THTH
THTT
TTHT
TTTH
TTTT
rrusczyk20:02:00
(I'm going to focus on the first flip in the 4-toss outcomes, instead of the last one. It's essentially the same thing.)
(I'm going to focus on the first flip in the 4-toss outcomes, instead of the last one. It's essentially the same thing.)
rrusczyk20:02:22
We see that 5 of the 4-toss outcomes start with T. Look at the remaining flips for those 5. What are they?
We see that 5 of the 4-toss outcomes start with T. Look at the remaining flips for those 5. What are they?
AIME_is_hard20:03:12
the 3-flip
the 3-flip
jvenezuela71620:03:12
HTH, HTT, THT, TTH, TTT... precisely the successful 3-toss outcomes.
HTH, HTT, THT, TTH, TTT... precisely the successful 3-toss outcomes.
rrusczyk20:03:15
They are just the 3-flip outcomes! That's because any time we have 3-toss outcome without HH, we can always put a T on front of it to get a 4-toss outcome without H!
They are just the 3-flip outcomes! That's because any time we have 3-toss outcome without HH, we can always put a T on front of it to get a 4-toss outcome without H!
rrusczyk20:03:18
So, we had:
So, we had:
rrusczyk20:03:25
Three toss outcomes without HH:
HTH
HTT
THT
TTH
TTT
Three toss outcomes without HH:
HTH
HTT
THT
TTH
TTT
rrusczyk20:03:31
Tack a T on to the front:
Tack a T on to the front:
rrusczyk20:03:34
THTH
THTT
TTHT
TTTH
TTTT
THTH
THTT
TTHT
TTTH
TTTT
rrusczyk20:03:43
We get 4-toss outcomes without HH.
We get 4-toss outcomes without HH.
rrusczyk20:04:05
Must every 4-toss outcome without HH that starts with T be producible from a 3-toss outcome without HH?
Must every 4-toss outcome without HH that starts with T be producible from a 3-toss outcome without HH?
crazypianist111620:04:44
yes
yes
vvipul20:04:44
yes. adding a t changes nothing about whether or not it has HH
yes. adding a t changes nothing about whether or not it has HH
rrusczyk20:04:45
Yes! If we take off that front T, we will only have 3 tosses, and we will not have an HH.
Yes! If we take off that front T, we will only have 3 tosses, and we will not have an HH.
rrusczyk20:05:09
So, we know that there are exactly as many 4-tosses that start with T as there are 3-tosses.
So, we know that there are exactly as many 4-tosses that start with T as there are 3-tosses.
rrusczyk20:05:20
We call this a 1-1 (one-to-one) correspondence.
We call this a 1-1 (one-to-one) correspondence.
jonathanyim20:05:23
why do we will not have HH??
why do we will not have HH??
rrusczyk20:05:36
Because we didn't have an HH to begin with, and all we did was remove the front T.
Because we didn't have an HH to begin with, and all we did was remove the front T.
rrusczyk20:05:53
So, we've dealt with the 4-toss outcomes that start with T.
So, we've dealt with the 4-toss outcomes that start with T.
rrusczyk20:06:00
Now, what about the ones that start with H?
Now, what about the ones that start with H?
rrusczyk20:06:04
HTHT
HTTH
HTTT
HTHT
HTTH
HTTT
rrusczyk20:06:12
There they are. What do we compare them to?
There they are. What do we compare them to?
vvipul20:06:32
the second must be T
the second must be T
lokito20:06:36
and the ones that start with H have a T and then a two-toss
and the ones that start with H have a T and then a two-toss
vvipul20:06:36
2-tosses
2-tosses
crazypianist111620:06:36
they start with ht followed by the two toss outcomes
they start with ht followed by the two toss outcomes
AIME_is_hard20:06:40
the 2-toss outcomes
the 2-toss outcomes
Hanthegreat20:07:07
the 2-toss outcomes
the 2-toss outcomes
rrusczyk20:07:14
Exactly. If the first flip is H, the second must be T, and then we can add any of our 2-toss outcomes to make a 4-flip outcome with no HH.
Exactly. If the first flip is H, the second must be T, and then we can add any of our 2-toss outcomes to make a 4-flip outcome with no HH.
rrusczyk20:07:17
We start with:
We start with:
rrusczyk20:07:20
Two toss outcomes without HH:
HT
TH
TT
Two toss outcomes without HH:
HT
TH
TT
rrusczyk20:07:28
And then add HT to the front of each, and we have:
And then add HT to the front of each, and we have:
rrusczyk20:07:31
HTHT
HTTH
HTTT
HTHT
HTTH
HTTT
rrusczyk20:07:58
So, the number of 4-toss outcomes that start with H equals the total number of 2-toss outcomes.
So, the number of 4-toss outcomes that start with H equals the total number of 2-toss outcomes.
rrusczyk20:08:23
So, if we let f(n) be the number of ways we can toss n coins without getting HH, what equation can we write for f(4)?
So, if we let f(n) be the number of ways we can toss n coins without getting HH, what equation can we write for f(4)?
jvenezuela71620:08:52
f(4)=f(2)+f(3)
f(4)=f(2)+f(3)
AIME_is_hard20:08:52
f(4)=f(3)+f(2)
f(4)=f(3)+f(2)
AIME_is_hard20:08:54
This is recursion!
This is recursion!
rrusczyk20:08:57
Exactly!
Exactly!
rrusczyk20:09:37
We just showed that all the 4-tosses that start with T equals the number of 3-tosses. And the number of 4-tosses that start with H equals the number of 2-tosses. Adding these together gives us all the 4-toss outcomes, so we have:
We just showed that all the 4-tosses that start with T equals the number of 3-tosses. And the number of 4-tosses that start with H equals the number of 2-tosses. Adding these together gives us all the 4-toss outcomes, so we have:
rrusczyk20:09:42
f(4) = f(3) + f(2).
f(4) = f(3) + f(2).
vvipul20:09:52
since there was nothing special about 4 in the problem we used, we can generalize that to n
since there was nothing special about 4 in the problem we used, we can generalize that to n
rrusczyk20:09:57
Exactly, and we get:
Exactly, and we get:
vvipul20:09:58
f(4)=f(3)+f(2) and generalizing, F(n)=f(n-1)+f(n-2))
f(4)=f(3)+f(2) and generalizing, F(n)=f(n-1)+f(n-2))
rrusczyk20:10:28
In just the same way, we can split n-toss outcomes into T+(an n-1 toss outcome) and HT+(an n-2 toss outcome).
In just the same way, we can split n-toss outcomes into T+(an n-1 toss outcome) and HT+(an n-2 toss outcome).
rrusczyk20:10:38
So, we have f(n) = f(n-1) + f(n-2).
So, we have f(n) = f(n-1) + f(n-2).
rrusczyk20:10:54
Just this recursion is not enough to guarantee we have Fibonacci numbers. What else must we check?
Just this recursion is not enough to guarantee we have Fibonacci numbers. What else must we check?
jvenezuela71620:11:42
f(1), f(2)
f(1), f(2)
jvenezuela71620:11:54
"Base cases", in a way.
"Base cases", in a way.
rrusczyk20:11:56
We must get the initial conditions -- the first couple outcomes. We already listed to see that f(1) =2, f(2) = 3. So, now we see that f(3) = f(2) + f(1) = 5, so f(4) = 5 + 3 = 8, and so on.
We must get the initial conditions -- the first couple outcomes. We already listed to see that f(1) =2, f(2) = 3. So, now we see that f(3) = f(2) + f(1) = 5, so f(4) = 5 + 3 = 8, and so on.
AIME_is_hard20:11:58
f(1) and f(2)
f(1) and f(2)
rrusczyk20:12:12
So, now we can just crank away to get f(10). What is it?
So, now we can just crank away to get f(10). What is it?
crazypianist111620:12:35
144
144
RedCardinal_220:12:35
144
144
jvenezuela71620:12:35
144
144
rrusczyk20:12:44
We crank out the terms, and we have the sequence
We crank out the terms, and we have the sequence
rrusczyk20:12:46
2, 3, 5, 8, 13, 21, 34, 55, 89, 144
2, 3, 5, 8, 13, 21, 34, 55, 89, 144
Hanthegreat20:12:58
f(10)
f(10)
AIME_is_hard20:12:58
144
144
Hanthegreat20:12:58
144
144
jonathanyim20:12:58
144
144
rrusczyk20:12:59
So, f(10) = 144.
So, f(10) = 144.
rrusczyk20:13:06
So, what is the answer to the problem?
So, what is the answer to the problem?
rrusczyk20:13:19
Here was the problem:
Here was the problem:
rrusczyk20:13:20
rrusczyk20:13:33
(Always read the question at the end to make sure you are answering what is asked!!!)
(Always read the question at the end to make sure you are answering what is asked!!!)
crazypianist111620:14:02
73
73
RedCardinal_220:14:02
73
73
rrusczyk20:14:07
We can now say that i/j = 144/1024 = 9/64, so i + j = 73.
We can now say that i/j = 144/1024 = 9/64, so i + j = 73.
AIME_is_hard20:14:11
9/64, so 9+64=73
9/64, so 9+64=73
rrusczyk20:14:14
This is one of those problems that shows how important it is to test small cases and then to observe the way that we generate those cases. Making the connection between the way we generated each new sequence and the recursion that we derived gave us a direct calculation to our answer.
This is one of those problems that shows how important it is to test small cases and then to observe the way that we generate those cases. Making the connection between the way we generated each new sequence and the recursion that we derived gave us a direct calculation to our answer.
rrusczyk20:14:49
This also is an example of how I usually prove recursions: I look at a simple case, as we did with 4-tosses, and I look for how it relates to even simpler cases.
This also is an example of how I usually prove recursions: I look at a simple case, as we did with 4-tosses, and I look for how it relates to even simpler cases.
jvenezuela71620:14:54
I wish I'd known recursion on last year's AIME. >.<
I wish I'd known recursion on last year's AIME. >.<
rrusczyk20:15:10
:) At least every other year there is a problem on the AIME that I just glance at and think, "recursion".
:) At least every other year there is a problem on the AIME that I just glance at and think, "recursion".
rrusczyk20:16:07
The biggest clue is that you have a setup that is essentially the same if you increase a number by 1 or 2, the way this problem is essentially the same if you do 11 flips or 12. Then, if that number is relatively low, you know you'll be able to crank out the answer once you get the recursion.
The biggest clue is that you have a setup that is essentially the same if you increase a number by 1 or 2, the way this problem is essentially the same if you do 11 flips or 12. Then, if that number is relatively low, you know you'll be able to crank out the answer once you get the recursion.
crazypianist111620:16:09
So the only way to find terms for this is just cranking them out? If they asked for the 80th toss, we would be hopeless?
So the only way to find terms for this is just cranking them out? If they asked for the 80th toss, we would be hopeless?
rrusczyk20:16:30
There is a formula for the Fibonacci numbers (google Binet), but it sure wouldn't make life easier here!
There is a formula for the Fibonacci numbers (google Binet), but it sure wouldn't make life easier here!
rrusczyk20:16:49
This problem is slightly harder than average than the ones we do in the AIME class (or maybe even just average).
This problem is slightly harder than average than the ones we do in the AIME class (or maybe even just average).
rrusczyk20:16:54
Are there any questions about the course?
Are there any questions about the course?
jvenezuela71620:17:10
Are there any graded assignments for this class?
Are there any graded assignments for this class?
rrusczyk20:17:31
No. This is a Problem Series class, which means we only have message board problems that the class discusses, but does not turn in.
No. This is a Problem Series class, which means we only have message board problems that the class discusses, but does not turn in.
AIME_is_hard20:17:34
How do we make up for the courses we miss?
How do we make up for the courses we miss?
rrusczyk20:18:05
There is a full transcript made of every class that you can access online within 24 hours after class ends (and the transcript stays up until about 4 weeks after the course ends).
There is a full transcript made of every class that you can access online within 24 hours after class ends (and the transcript stays up until about 4 weeks after the course ends).
crazypianist111620:18:08
Will this class help for the last few problems of AMC 12?
Will this class help for the last few problems of AMC 12?
rrusczyk20:18:10
Yes.
Yes.
jonathanyim20:18:12
what is a formula for Fibonacci numbers???
what is a formula for Fibonacci numbers???
rrusczyk20:18:16
Google Binet.
Google Binet.
EMetz20:18:18
how much material is different than that covered in AoPS vol 2?
how much material is different than that covered in AoPS vol 2?
rrusczyk20:18:54
There is an overlap in the basic ideas, but mainly this class strictly focuses on problems. (Also, there are AIME-like problems in Vol 2, but no actual AIME problems, so you won't have an overlap in problems.)
There is an overlap in the basic ideas, but mainly this class strictly focuses on problems. (Also, there are AIME-like problems in Vol 2, but no actual AIME problems, so you won't have an overlap in problems.)
AIME_is_hard20:18:56
Will there be some problems given for us to do outside of class?
Will there be some problems given for us to do outside of class?
rrusczyk20:19:17
Yes. Every week, we post 10-12 extra problems on the message board for you to discuss (at the end of the week, we post the solutions.)
Yes. Every week, we post 10-12 extra problems on the message board for you to discuss (at the end of the week, we post the solutions.)
AIME_is_hard20:19:37
About how many people are taking this class?
About how many people are taking this class?
rrusczyk20:19:55
No idea. I expect it to be several dozen; it's one of our more popular classes.
No idea. I expect it to be several dozen; it's one of our more popular classes.
crazypianist111620:20:05
How much time does it require per week on average?
How much time does it require per week on average?
rrusczyk20:20:59
You should expect to spend around 4 hours a week (including class time) to get the most out of the course. (Some students spend a little more, others coast by doing little and not learning much.)
You should expect to spend around 4 hours a week (including class time) to get the most out of the course. (Some students spend a little more, others coast by doing little and not learning much.)
bowser20:21:01
if a lot of people take it will the class be divided like the intro to counting and probability class
if a lot of people take it will the class be divided like the intro to counting and probability class
rrusczyk20:21:03
Yes.
Yes.
bowser20:21:41
DO THE MATH!!! XD
DO THE MATH!!! XD
rrusczyk20:21:57
That's good advice. History class is a good time to do that. (Worked for me.)
That's good advice. History class is a good time to do that. (Worked for me.)
jonathanyim20:22:23
What are we doing right now??
What are we doing right now??
rrusczyk20:22:34
Question and answer about the course. We won't be doing any more math.
Question and answer about the course. We won't be doing any more math.
AIME_is_hard20:22:56
I am considering taking the mastering mathcounts course, but i am afraid it will conflict with this course.
I am considering taking the mastering mathcounts course, but i am afraid it will conflict with this course.
rrusczyk20:23:39
These classes are wildly different in difficulty -- the AIME course is much, much harder. That's why we put them at the same time -- very few students would want to take both.
These classes are wildly different in difficulty -- the AIME course is much, much harder. That's why we put them at the same time -- very few students would want to take both.
dtl4220:23:41
So the material is completely different from Series A? in terms of problems?
So the material is completely different from Series A? in terms of problems?
rrusczyk20:23:47
Yes, in terms of problems.
Yes, in terms of problems.
rrusczyk20:24:12
Are there any more questions about the AIME class?
Are there any more questions about the AIME class?
crazypianist111620:24:28
is it fun?
is it fun?
rrusczyk20:24:31
It's a blast.
It's a blast.
Charliex20:24:57
are the problems we do logic or based on whether we know the subject or not
are the problems we do logic or based on whether we know the subject or not
rrusczyk20:25:06
You have to have the fundamentals down, for sure.
You have to have the fundamentals down, for sure.
jvenezuela71620:25:08
Is there any overlap with WOOT in terms of concepts?
Is there any overlap with WOOT in terms of concepts?
rrusczyk20:25:37
There's some overlap, for sure, but there's more focus here on the fundamental AIME-like tools, and not so much on rigor and proof like you have in WOOT.
There's some overlap, for sure, but there's more focus here on the fundamental AIME-like tools, and not so much on rigor and proof like you have in WOOT.
Charliex20:26:40
are we going to learn shortcuts or the long elaborated equations for problems
are we going to learn shortcuts or the long elaborated equations for problems
rrusczyk20:26:42
Don't think of them as shortcuts -- you will learn general methods. Not things to memorize. You can't memorize your way through the AIME. That is why it is a good test.
Don't think of them as shortcuts -- you will learn general methods. Not things to memorize. You can't memorize your way through the AIME. That is why it is a good test.
rrusczyk20:27:27
That's it for the Math Jam tonight. If you have any more questions about the class, you can reach us at classes@artofproblemsolving.com. Thanks for coming!!
That's it for the Math Jam tonight. If you have any more questions about the class, you can reach us at classes@artofproblemsolving.com. Thanks for coming!!
Copyright © 2024 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.
