| Transcript
for the Math
Jam "AoPS Classes Math Jam"
on Nov 15. |
| Math Jam hosted by Valentin Vornicu
(Valentin Vornicu ). |
rrusczyk19:48: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.
rrusczyk19:48:29
The classroom is moderated: students can type into the classroom, but only the moderators can choose a comment to drop into the classroom. 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:48:41
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.
rrusczyk19:48:55
In addition, 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:48:59
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:49:05
rrusczyk19:49:14
This message will look like this when posted in the classroom:
rrusczyk19:49:20
rrusczyk19:49:26
Just remember, if your post uses LaTeX, use the semicolon (;) to begin your post!
rrusczyk19:49:42
Are there any questions about how the class operates before we get started?
Aquila19:50:19
Do you prefer that we type everything in LATEX?
rrusczyk19:50:33
Actually, I prefer you only use LaTeX if you need to, and know how to.
rrusczyk19:50:37
Text is fine.
rrusczyk19:51:08
The AIME Problem Series will be taught by Valentin Vornicu. The course begins Thursday, November 29, and classes are Thursday nights from 7:30 to 9 PM ET (4:30 to 6 PM PT).
rrusczyk19:51:22
Valentin is a 2-time member of the Romanian IMO team.
rrusczyk19:51:31
In the AIME Problem Series, we will be looking at problems that almost all come from the AIME contest.
krakola4519:51:45
Is this Problem Series a or B
rrusczyk19:51:55
It is AIME Problem Series B.
rrusczyk19:52:07
It is not the same as the Problem Series over the summer.
arpitpanda19:52:21
What is the duration of the course
rrusczyk19:52:36
There are 12 classes. The course will end just before the first AIME in March.
rrusczyk19:52:44
We will not have class during the holidays.
wgpark0924_219:52:56
what's the difference of problem series A and B?
rrusczyk19:53:28
There's basically no difference in difficulty or in subject coverage - we just discuss different problems in the two classes.
rrusczyk19:54:15
Before I dive into a couple problems, are there any questions about Art of Problem Solving courses?
arpitpanda19:54:25
Approximately how many problems do you guys discuss?
rrusczyk19:54:55
Each class covers 5-12 questions, depending on how hard the problems are. (Some classes focus on really hard problems, others have a wider variety of difficulty.)
krakola4519:54:57
Is the AIME Problem Series A after the AIME I or before the AIME I
rrusczyk19:55:09
We won't offer AIME Problem Series A again until next summer.
Zmastr19:55:11
Is there homework?
rrusczyk19:55:27
After each class, we post a series of practice problems on the message board for students to discuss on the message board.
rrusczyk19:55:35
This is the 'homework', but it is not turned in.
arpitpanda19:55:55
What kind of students should go for this class?
rrusczyk19:56:21
Mainly, students who think they are 'on the borderline' for passing the AIME.
rrusczyk19:56:34
These are students who might score 3-9 on practice AIMEs now.
rrusczyk19:56:46
If you're consistently getting 10-12 on the AIME, you should be practicing for the olympiad.
rrusczyk19:57:06
If you're not likely to pass the AMC 10 or AMC 12, you should probably start at that level.
Ovrlndnsea19:57:11
so no midterm or finial like other classes?
rrusczyk19:57:17
That is correct. No midterm or final.
Darklegacy5219:57:38
i am also in the amc10 class and just in case of a technical issue..when i click classroom on the homepage will the correct one open up?
rrusczyk19:57:53
The classes are not on the same day, so yes. You will go right into the correct classroom.
Phred19:57:55
Are the classes different from year to year?
rrusczyk19:58:07
They are not. But the AIME A and AIME B Problem Series are different.
Aquila19:58:13
What if I have never taken the AIME. Where can I find a practice test?
rrusczyk19:58:32
You can find several on the AoPSWiki.
rrusczyk19:58:53
Click on AoPSWiki on the sidebar.
rrusczyk19:59:00
Then search around for the AIME.
rrusczyk19:59:04
Any more questions?
rrusczyk19:59:29
Let's do a couple problems.
rrusczyk19:59:40
These are similar to the types of problems we discuss in the course.
rrusczyk19:59:57
rrusczyk20:00:18
Where might we start?
krakola4520:00:36
listing a few terms
rrusczyk20:00:53
In general, looking at little numbers is a good start with lots of problems.
rrusczyk20:00:59
But here, it gets scary pretty fast!
rrusczyk20:01:23
We don't have calculators on the AIME, so we can't pound out 6^5 and 8^5 really easily.
mathforme20:01:50
alkjash20:01:50
Find a pattern for both 6 and 8 seperately
alkjash20:01:59
Find the remainders of 6^83 and 8^83 divided by 49.
rrusczyk20:02:26
We could go after that, but why is it a little daunting to go after remainders when dividing by 49?
alkjash20:02:56
It's a large number
rrusczyk20:03:00
There are a lot of possible remainders - it could be plenty hard to find a pattern!
rrusczyk20:03:07
What might we try to do instead?
unimpossible20:03:17
(7-1) and (7+1)
rrusczyk20:03:31
And then what?
rrusczyk20:04:32
We might think to write 6 as 7-1 and 8 as 7+1, since we are interested in dividing 6^83 + 8^83 by 7^2.
rrusczyk20:04:53
edwarddinh20:05:13
use binomial theorem
rrusczyk20:05:17
Let's give that a try:
rrusczyk20:05:26
rrusczyk20:05:34
rrusczyk20:05:46
Now what?
alkjash20:06:14
Expand it and take out all terms with more than 2 7s as factors
arpitpanda20:06:14
the positive and negative terms cancel out
wgpark0924_220:06:14
49 = 7^2
Phred20:06:14
cancel alterntating terms
krakola4520:06:14
canceling out
rrusczyk20:06:42
We add, lots of things cancel out, and we can:
alkjash20:06:44
Only look at 7^1 and 7^0 terms
edwarddinh20:07:05
ignore all powers of 7 bigger than 1 because they would be 0(mod49)
rrusczyk20:07:09
All the terms with factors of 7^n for n > 1 are divisible by 49. So we can ignore them.
rrusczyk20:07:13
What are we left with?
edwarddinh20:07:48
83(7)(2)
rrusczyk20:07:52
rrusczyk20:08:00
So, what is our final answer?
Phred20:08:47
35
alkjash20:08:47
35
rrusczyk20:08:56
Our final answer is the remainder when 1162 is divided by 49, which is 35.
rrusczyk20:09:15
An important AIME point: Be very careful when performing computations. Take your time, write neatly.
rrusczyk20:09:31
Far too many students miss passing the AIME due to careless calculation errors.
rrusczyk20:09:54
I strongly advise you read the article Stop Making Stupid Mistakes in our Resources->Articles section of our website.
rrusczyk20:10:14
I used to make careless errors all the time.
rrusczyk20:10:22
Then I started doing what I describe in that article.
rrusczyk20:10:53
I scored the only 15 in the country on the AIME in my senior year, and much of the reason is that I got rid of my careless mistakes.
rrusczyk20:10:57
That article describes how.
rrusczyk20:11:15
Any questions about that first problem? (We'll look at one more, then take more questions about the class.)
Zmastr20:11:43
how am i supposed to know the binomial theorem?
rrusczyk20:12:27
The Binomial Theorem is one of the subjects that AIME test writers will assume students know. You can learn about it in our Introduction to Counting & Probability class (and book), and we will cover more advanced applications of it in our Intermediate Algebra book (and class).
rrusczyk20:12:42
Let's look at the next problem!
rrusczyk20:12:44
rrusczyk20:13:17
There are 2^10 = 1024 possible outcomes for the series of ten tosses. How can we count the number of tosses that include no consecutive heads?
rrusczyk20:13:23
Where might we start?
rrusczyk20:14:00
I see a number of you suggesting casework.
rrusczyk20:14:13
Before we jump back into the problem, I'd like to make a few notes about casework.
rrusczyk20:14:27
First, if you are going to use casework, you must be very careful.
rrusczyk20:15:06
It will often work (particularly on AIME problems), but you have to make sure you have described every possible case, and that each possibility you wish to count is only counted once (i.e., you don't overcount).
rrusczyk20:15:32
I usually only jump into casework when either (a) I see a clear path to the solution or (b) I can't find a clever way to do it.
rrusczyk20:15:50
Here, we can start by looking for a clever solution like this:
alkjash20:15:54
Try it with smaller number of coin tosses
rrusczyk20:16:21
We could begin by examining smaller sequences of tosses.
rrusczyk20:16:25
One toss outcomes without HH:
H
T
rrusczyk20:16:29
Two toss outcomes without HH:
HT
TH
TT
rrusczyk20:16:34
In what ways could we toss a coin three times without ending up with HH in the sequence?
Zmastr20:17:34
TTT, HTT, THT, TTH, HTH
edwarddinh20:17:34
HTH
HTT
TTT
THT
TTH
Phred20:17:34
ttt, tth, tht, htt, hth
BlueOrb20:17:34
HTT, HTH, THT, TTH, TTT
rrusczyk20:17:39
Three toss outcomes without HH:
HTH
HTT
THT
TTH
TTT
rrusczyk20:17:46
How about four coins?
Ovrlndnsea20:19:00
HTHT
HTTH
THTH
HTTT
THTT
TTHT
TTTH
TTTT
rrusczyk20:19:05
Four toss outcomes without HH:
HTHT
HTTH
HTTT
THTH
THTT
TTHT
TTTH
TTTT
rrusczyk20:19:43
Now, we could have started from scratch to find this list.
rrusczyk20:19:59
Or instead, what could we have done to quickly find the four-toss outcomes?
Ovrlndnsea20:20:06
2,3,5,8... Fibbonacci?
rrusczyk20:20:17
(Interesting observation - always look for patterns.)
rrusczyk20:20:33
But, how could we have quickly found our list from 4 tosses:
rrusczyk20:20:35
Four toss outcomes without HH:
HTHT
HTTH
HTTT
THTH
THTT
TTHT
TTTH
TTTT
rrusczyk20:20:53
Without just starting from scratch listing possibilities? (You can look at our earlier lists.)
alkjash20:21:32
Adding onto the earlier lists
Phred20:21:32
add a T or an H to a list ending in T or just a T to a list ending in H
rrusczyk20:21:37
Exactly.
rrusczyk20:21:39
We can start from this list:
rrusczyk20:21:43
Three toss outcomes without HH:
HTH
HTT
THT
TTH
TTT
rrusczyk20:22:01
We can start from this to build our 4-toss list:
Ovrlndnsea20:22:03
add a T to the begining of every 3-toss and add an H to the begining of every 3-toss that begins with T
rrusczyk20:22:12
If we add one flip to a sequence that ends in H, the new flip must be a T or the sequence will end in HH.
rrusczyk20:22:16
If we add one flip to a sequence that ends in T, the new flip can be either a T or an H and there is no new occurrence of HH.
rrusczyk20:22:29
Aha! We have a way to relate the 4-toss list to the 3-toss list.
rrusczyk20:22:38
What counting tactic does this suggest?
edwarddinh20:23:34
recurrence?
rrusczyk20:23:56
We build 4-flips from 3-flips.
rrusczyk20:24:04
We can similarly build 5-flips from 4-flips.
rrusczyk20:24:07
And so on.
rrusczyk20:24:13
This is a classic recursion.
rrusczyk20:24:24
So let's set it up.
rrusczyk20:24:26
How?
rrusczyk20:25:23
We build our 4-toss list by breaking our 3-toss list into two groups; what are these two groups?
edwarddinh20:25:46
ending in T or ending in H
alkjash20:25:46
Those that end in H and those that end in T
Aquila20:25:53
Those that end in H and in T
rrusczyk20:26:08
Exactly. So, we have a variable for each.
rrusczyk20:26:15
rrusczyk20:26:53
What equations can we write in terms of a's and b's?
alkjash20:27:52
b_n+1 = a_n + b_n
rrusczyk20:27:54
Why?
rrusczyk20:27:56
Why?
alkjash20:29:14
Because there will be another sequence ending with tails for each of the shorter sequences.
rrusczyk20:29:25
rrusczyk20:29:48
Or, as alkjash more succinctly put it, we get a sequence with n flips that ends in T by adding a T to any of the n-1 flip sequences.
rrusczyk20:30:09
Can we find another equation?
alkjash20:30:11
And a_n+1 = b_n
Phred20:30:11
a_n+1=b_n
rrusczyk20:31:20
rrusczyk20:31:36
rrusczyk20:31:40
Now what?
alkjash20:32:26
So now we start with a_1 and b_1 and work up?
Aquila20:32:26
We can put 1 in for n to start
edwarddinh20:32:26
since we have b_4 and a_4
rrusczyk20:32:43
We could indeed work our way up, but does anyone see a slick substitution we can make?
rrusczyk20:32:54
(That will help simplify the work)
edwarddinh20:33:17
b_n=b_n-2+b_n-1
rrusczyk20:33:32
rrusczyk20:33:38
Look familiar?
edwarddinh20:33:50
fibonacci
alkjash20:33:50
yea fibonacci
arpitpanda20:33:50
fibonacci
rrusczyk20:34:01
BlueOrb20:34:45
It is equal to b_(n-1) so it is a Fibbonacci sequence one term behind a_n.
rrusczyk20:35:00
Zmastr20:35:10
whoa ovrlandnsea is a prophet!
rrusczyk20:35:14
Indeed :)
rrusczyk20:35:19
How can we use these facts to help us solve the problem?
edwarddinh20:35:56
so we plug in n=10 to find i
edwarddinh20:35:56
and we know j=1024
edwarddinh20:35:56
and simplify
alkjash20:35:56
Write out fibonnaci and find the twelth term
rrusczyk20:36:07
Now we can pound it out. What do we get as our answer?
mathforme20:36:28
Oops! I got 9/64, so I think the answer is 73
Zmastr20:36:28
9/64 :)
rrusczyk20:36:39
rrusczyk20:36:51
We can now say that i/j = 144/1024 = 9/64, so i + j = 73.
rrusczyk20:36:57
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:37:54
Recursion is one of my favorite counting tactics, and it pops up pretty frequently on the AIME. Any time a problem is essentially the same whether a key number in a problem is one higher or one lower, you might think to try recursion.
rrusczyk20:37:56
Any questions?
alkjash20:38:17
About the question or class?
rrusczyk20:38:23
Either.
Aquila20:38:41
On average what rank in difficulty would you give the previous problom in the AIME?
rrusczyk20:39:04
The first problem is probably an early AIME problem, say #3 or 4.
rrusczyk20:39:19
The second is middle-late, say number 8 or 9.
alkjash20:39:21
On which days are the classes?
rrusczyk20:39:27
The classes are on Thursdays.
Zmastr20:40:19
Not to sound insulting, but why are you doing the intro class and not Valentin, if he's going to be doing the other classes?
rrusczyk20:40:35
Val is busily working on the new server, so I'm covering for him.
rrusczyk20:40:54
Are there any more questions?
Darklegacy5220:42:02
how long do we have for the aime?
rrusczyk20:42:04
3 hours.
Aquila20:42:06
Are there any Middle School students that are qualified to attend this class?
rrusczyk20:42:38
Yes. Not many, but they exist. I would only recommend this class for a middle school student if the student has already passed the AMC (or has no problem with practice AMC tests).
rrusczyk20:43:22
In general, I recommend most middle school students start with our Introduction level subject classes, but there are certainly some middle school students (such as those who already took those classes:) ) who are ready for more challenging material.
arpitpanda20:43:38
Can you expect nice patterns like the fibonacci to turn up on AIME problems. Or do things tend to work out nicely or not really.
rrusczyk20:43:48
You should always keep your eyes open for patterns.
rrusczyk20:44:04
Squares, cubes, Fibonacci numbers, triangular numbers - these pop up all over.
Darklegacy5220:44:18
what are triangular numbers?
mathforme20:44:28
What are triangular numbers?
rrusczyk20:44:35
How many dots are in this triangle:
rrusczyk20:44:39
.
..
...
Aquila20:45:03
rrusczyk20:45:09
.
..
...
....
rrusczyk20:45:17
How many?
Darklegacy5220:45:21
10
Aquila20:45:21
mathforme20:45:29
4(4+1)/2 = 10
alkjash20:45:29
10
rrusczyk20:45:31
And so on.
rrusczyk20:45:39
These are the triangular numbers.
rrusczyk20:45:54
I'll let you work on your own to find a formula for them.
rrusczyk20:46:08
Then, try to find a formula for the sum of the first n triangular numbers!
rrusczyk20:46:14
(On your own!)
alkjash20:46:36
Aren't they the diagonals of pascals triangle?
rrusczyk20:46:50
Yes - see if you can figure out why. (on your own)
rrusczyk20:47:02
Thanks for coming tonight. You can email us at classes@artofproblemsolving.com if you have any more questions about this or any other class.
rrusczyk20:47:16
A transcript of this Math Jam will be available on the site in about 15 minutes.
arpitpanda20:47:34
Quick aside, but do 11 and 12 graders have to score very high on the AMC-12 as well as the AIME to qualify for USAMO
rrusczyk20:47:44
Yes, that is true - you need to have a high combined AMC and AIME score.
llolloll20:48:23
what's the lower bound limit?
Darklegacy5220:48:23
what would be considered high?
rrusczyk20:49:00
Varies greatly from year to year. Art of Problem Solving sponsored an expansion from 250 USAMO participants to 500 participants, so the score you need is a lot lower than it used to be.
Aquila20:49:02
Is the AIME a "fill in the bubble" test
rrusczyk20:49:18
Yes- every answer is an integer from 0 to 999.
rrusczyk20:49:25
You bubble the integer answer in.
llolloll20:49:33
what about for the AMC 10?
rrusczyk20:49:35
Varies widely from year to year.
Darklegacy5220:50:44
so we need to include a 0 in front of 2 digit numbers?
rrusczyk20:50:54
Yes. Read the instructions on the test closely!
Cosette Barnett20:50:56
thanks for having us for your math jam
rrusczyk20:50:59
Thank you for coming!
rrusczyk20:51:37
If you have any more questions, you can email us at classes@artofproblemsolving.com, or post on the message board (the Director of the AMC frequently answers questions about the AMC on the AMC Forum on our site.)
rrusczyk20:51:46
Thanks for coming - see you all later!
