| Transcript
for the Math
Jam "AoPS MATHCOUNTS and AIME B Problem Series"
on Nov 7. |
| Math Jam hosted by rrusczyk
(Richard Rusczyk ). |
rrusczyk (19:29:45)
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.
rrusczyk (19:29:51)
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.
rrusczyk (19:29:58)
In addition, the virtual classroom is TeX enabled. TeX allows users to make nice equations and other math expressions. If you would like to learn how to write in TeX/LaTeX, click on the tab on the left side panel of our site and there is a tutorial and reference guide there.
rrusczyk (19:30:03)
Using TeX in the virtual classroom is slightly different than using it on the message board or in a TeX editor. If anything you type up in a post that uses TeX then you must use a semicolon (;) to begin your post. For example, if you type
rrusczyk (19:30:07)
rrusczyk (19:30:11)
This message will look like this when posted in the classroom:
rrusczyk (19:30:16)
rrusczyk (19:30:23)
Just remember, if your post uses TeX, use the semicolon (;) to begin your post!
rrusczyk (19:30:37)
Today we will be discussing the MATHCOUNTS Problem Series and the AIME Problem Series B.
rrusczyk (19:30:48)
The MATHCOUNTS Problem Series is a 12 week course designed to cover one by one the areas of problem solving covered by the MATHCOUNTS competition. Topics covered including methods of counting, probability, algebraic techniques, word problems, number theory, and more.
rrusczyk (19:30:54)
I am the instructor of the MATHCOUNTS Problem Series. The course begins Monday, November 20, and ends on February 26. Classes are Monday nights from 7:30 until 9 PM ET (4:30 to 6 PM PT).
rrusczyk (19:31:15)
We will now go through a few problems like those we will tackle in the course, then I will take questions about the course if you have any.
rrusczyk (19:31:34)
Here's the first question; a bit of a warm-up:
rrusczyk (19:31:36)
rrusczyk (19:31:51)
Where can we start with this problem?
MichaelFaraday (19:32:15)
p, and p+1 are 2 and 3
buzzer11 (19:32:17)
is p and p+1 2 and 3?
rrusczyk (19:32:31)
Since either p or p + 1 is even, one of them must be even, so one of them must be 2, the only even prime. Since 1 isn?t prime, the other one must be 3.
Now, how do we find the smallest composite number that is neither a multiple of 2 nor 3?
rrusczyk (19:33:21)
I see a lot of you suggesting primes.
rrusczyk (19:33:36)
We are asking for the smallest positive COMPOSITE number.
stargate (19:33:07)
a square number
stargate (19:33:36)
25
rrusczyk (19:33:53)
Why?
mathquests (19:34:55)
we rule out all even numbers
HoratioK (19:33:26)
It must be odd.
rrusczyk (19:35:25)
Good - all even numbers are multiples of 2, so we rule those out. What else?
mathprincess (19:35:26)
and all numbers disivible by three
Bart133 (19:35:34)
rule out multiples of 3
rrusczyk (19:35:45)
Yep, we toss out the multiples of 3. What else?
HoratioK (19:35:49)
Primes
rrusczyk (19:36:01)
Out go the primes.
rrusczyk (19:36:05)
So, what's our number?
buzzer11 (19:35:55)
it must be able to be factored into primes that are not 2 or 3
Bart133 (19:35:08)
5 is the best prime, but 25 is 5 squared.
HoratioK (19:35:43)
All numbers less than 25 are either prime or divisible by 2 or 3.
HoratioK (19:36:10)
The smallest number left is 25
rrusczyk (19:36:22)
rrusczyk (19:36:33)
Any questions about that problem?
rrusczyk (19:36:56)
The key was simply to read the question carefully. This is often the case with MATHCOUNTS problems, particularly target round problems.
rrusczyk (19:37:10)
Let's try another problem!
rrusczyk (19:37:11)
rrusczyk (19:38:09)
How do we start? Can we identify one of the three numbers?
HoratioK (19:37:38)
One prime must be 2, because 30 is even.
mathprincess (19:38:06)
you have to use 2
stargate (19:38:17)
2
i_like_pie (19:38:18)
One of the primes must be 2.
rrusczyk (19:38:26)
No matter what, one of the primes must be 2. If we have 3 numbers with an even sum, at least one of them is even. There's only one positive even prime, and that's 2.
rrusczyk (19:38:31)
So now what must we do?
HoratioK (19:38:30)
The other two must add to 28.
stargate (19:38:49)
the two other primes must add up to 28
mathprincess (19:38:53)
two prime numbers that add up to 28
mathquests (19:39:00)
The sum of the other primes=28
rrusczyk (19:39:12)
We must find the largest possible product of two primes which have a sum of 28.
rrusczyk (19:39:16)
We could list out the cases - what are our only options?
mathquests (19:39:28)
23 & 5
jds4prez (19:39:29)
11, 17
jds4prez (19:39:34)
11 and 17
rrusczyk (19:39:50)
Our only options are 11 & 17, and 5 & 23.
rrusczyk (19:39:58)
Which has a larger product?
i_like_pie (19:39:07)
The other two must be as close as possible.
mathprincess (19:39:11)
the two that have the least difference
mathprincess (19:39:22)
I like 17 and 11
jds4prez (19:39:52)
11, 17
CSSMARTZ (19:39:56)
11, 17
HoratioK (19:40:03)
11*17
buzzer11 (19:40:03)
11 and 17
rrusczyk (19:40:14)
rrusczyk (19:40:17)
What is the answer to the problem?
stargate (19:40:24)
374
HoratioK (19:40:32)
The answer is 374.
daveshail (19:40:36)
374
jds4prez (19:40:37)
374
rrusczyk (19:40:44)
rrusczyk (19:41:15)
Now we'll try a couple of the harder MATHCOUNTS problems. These are the types of problems that might show up at Nationals.
rrusczyk (19:41:21)
rrusczyk (19:41:25)
This is a tougher problem than most similar problems at MATHCOUNTS. In fact, I took the last question on a sprint round and added 'that are even'. But I wanted you all to take a shot at a problem that requires a little more thought than plugging into a formula.
rrusczyk (19:41:39)
First, how many positive integral divisors does 792 have?
daveshail (19:41:47)
prime factorization
rrusczyk (19:42:05)
What is the prime factorization of 792?
stargate (19:42:29)
2^3*3^2*11
buzzer11 (19:42:42)
HoratioK (19:42:45)
2*2*2*3*3*11
rrusczyk (19:42:54)
rrusczyk (19:43:40)
Can have 7 among its prime divisors?
HoratioK (19:43:44)
No
stargate (19:43:44)
no
buzzer11 (19:43:51)
no
rrusczyk (19:44:23)
The prime 7 doesn't divide 792, so a divisor of 792 cannot be divisible by 7.
rrusczyk (19:44:38)
At most how many 3's can be in the prime factorization of 792?
HoratioK (19:44:42)
2
stargate (19:44:42)
2
Bart133 (19:44:43)
2
rrusczyk (19:45:23)
rrusczyk (19:46:17)
rrusczyk (19:46:33)
So, how many choices do we have for the a?
cynthiaday (19:46:45)
4
rrusczyk (19:47:06)
Why not only 3?
Bart133 (19:47:22)
Because 0 [i]is [/i]a number.
cynthiaday (19:47:25)
Because there can be 0.
mathprincess (19:47:27)
because we can use 0
rrusczyk (19:48:12)
Right. Since a can be no more than 3, we have 4 choices (0, 1, 2, 3). (We are counting all the divisors of 792 first. We'll come back to the problem in a minute.)
rrusczyk (19:48:23)
How many choices do we have for b? How many for c?
Bart133 (19:48:28)
You have [b]3 [/b]choices for b and [b]2 [/b]for c by the same reason.
buzzer11 (19:48:37)
3 and 2, respectively
stargate (19:48:39)
3 for b 2 for c
Just4Math (19:48:39)
3 for b, 2 for c
rrusczyk (19:48:46)
rrusczyk (19:48:58)
So, how many divisors of 792 are there total?
stargate (19:49:07)
24
i_like_pie (19:49:08)
24
Just4Math (19:49:10)
24?
buzzer11 (19:49:12)
3*2*4
rrusczyk (19:49:28)
rrusczyk (19:49:42)
Now, how do we adjust this to count even divisors?
buzzer11 (19:49:53)
a cannot be zero
Bart133 (19:49:57)
It must only have 3 choices for a
i_like_pie (19:49:59)
a can't be 0
rrusczyk (19:50:27)
The even divisors have a positive exponent for the prime 2. So, for even divisors, a can be 1, 2, or 3. How many total even divisors are there?
buzzer11 (19:50:01)
so 3*3*2
Bart133 (19:50:11)
So there are 18 divisors.
i_like_pie (19:50:41)
18
rrusczyk (19:50:58)
rrusczyk (19:51:04)
Any questions about that problem?
jdmae86_2 (19:51:32)
why 0 cant be a?
rrusczyk (19:51:45)
We are counting *even* divisors.
Bart133 (19:51:50)
Because then it wouldn't be even.
rrusczyk (19:52:19)
Therefore, the exponent of 2 in an even number's prime factorization must be nonzero.
mathprincess (19:51:27)
what are the 6 numbers that are odd??
rrusczyk (19:52:35)
Can anyone name them?
HoratioK (19:52:39)
1,3,9,11,33,99
Just4Math (19:52:59)
1, 3, 9, 11, 33, 99
daveshail (19:53:10)
1.3.9.11.33.99
rrusczyk (19:53:18)
Good.
rrusczyk (19:53:39)
Since they are divisors of 792, they have prime factorization (2^a)(3^b)(11^c).
rrusczyk (19:53:45)
Since they are odd, a=0.
rrusczyk (19:53:57)
We know that b is at most 2 and c is at most 1. We use this to make our list.
rrusczyk (19:54:06)
Here's the last problem.
rrusczyk (19:54:07)
rrusczyk (19:54:39)
We could convert to base 10 first, but that looks pretty scary doesn't it?
rrusczyk (19:55:11)
What observation can we make about the numbers in the problem that might help us?
buzzer11 (19:55:13)
does it have anything to do with the fact that 9 is a multiple of 3?
rrusczyk (19:55:38)
9 is indeed a multiple of 3. Even more interesting:
HoratioK (19:55:31)
i_like_pie (19:55:32)
3 squared is 9
rrusczyk (19:55:47)
rrusczyk (19:56:04)
So, returning to the problem, what is our original number in terms of powers of 3?
Bart133 (19:54:56)
it's 2*3^0 + 1*3^2 + 2*3^5 + 2*3^6
rrusczyk (19:57:14)
rrusczyk (19:57:20)
rrusczyk (19:57:54)
We want to convert this to base 9. So, we want to write it in terms of powers of 9.
rrusczyk (19:58:06)
How do we do it?
buzzer11 (19:57:11)
which is 2 + 1*9 + 2*3^5 + 2*9^3 ?
rrusczyk (19:58:58)
Good. 3^6 = (3^2)^3 = 9^3. Similarly, 3^2 = 9^1. So, we can turn some of our terms directly into powers of 9.
rrusczyk (19:59:24)
But. . . What about that 2*3^5 term. How do we handle that?
Bart133 (19:59:09)
2*3^5 = 6*9^2
Bart133 (19:59:37)
It's 2*3^1*9^2.
HoratioK (19:59:49)
rrusczyk (20:00:00)
Bart133 (19:57:51)
or 2*9^0 + 1*9^1 + 6*9^2 + 2*9^3
rrusczyk (20:00:19)
So, what is our number in base 9?
Bart133 (20:00:22)
2612
jds4prez_2 (20:00:27)
2612
i_like_pie (20:00:27)
2612
rrusczyk (20:00:34)
rrusczyk (20:01:15)
So, understanding how number bases works saves a lot of time and removes a lot of chance for error!
rrusczyk (20:01:30)
Any questions?
rrusczyk (20:02:26)
The last two problems are on the harder end of problems we will do in the MATHCOUNTS course. In many problems, we will look at a variety of ways to solve the problem, and in some, we will focus on particularly fast ways to solve the problem, as we did here.
Just4Math (20:02:12)
if the base x number was not a sqr of another base y number, is there a short cut for that as well?
rrusczyk (20:02:44)
Not really - you have go through bas e10.
Bart133 (20:02:28)
I took each term as a power of 9. the 3^0 was 9^0. the 3^2 was 9^1. the 3^5 was 3*9^2. the 3^6 was 9^3.
rrusczyk (20:02:55)
Excellent.
mathquests (20:02:49)
what book will you be following?
rrusczyk (20:03:23)
We will not be following a specific textbook for this course. We will be using a selection of problems that mostly come from past MATHCOUNTS contests.
Bart133 (20:03:08)
Are there any more problems?
rrusczyk (20:03:42)
We will do AIME problems after the question and answer session about the MATHCOUNTS class.
buzzer11 (20:02:56)
how about cubes?
rrusczyk (20:03:52)
See if you can figure out how that works!
rrusczyk (20:04:04)
For example, convert 101111011 in base 2 to base 8
rrusczyk (20:04:25)
Are there any questions about the MATHCOUNTS Problem Series?
mathquests (20:04:14)
Are AIME problems harder than Mathcounts?
rrusczyk (20:04:34)
Yes, much harder.
rrusczyk (20:04:56)
The AIME is the second of the series of tests that determines the US Math Team for high school students.
Bart133 (20:04:18)
573
HoratioK (20:04:24)
573
rrusczyk (20:05:29)
(That's the answer to the base 2->base 8 question.)
Bart133 (20:04:49)
What does AIME stand for?
rrusczyk (20:05:40)
American Invitational Mathematics Exam.
Bart133 (20:05:35)
So when is the MATHCOUNTS question and answer session?
rrusczyk (20:05:54)
Right now - are there any questions about the MATHCOUNTS Problem Series?
stargate (20:05:43)
what in number theory would we be doing
rrusczyk (20:06:34)
We'll be doing a lot about divisors, primes, introducing modular arithmetic. We'll do problems involving least common multiple, etc.
mathprincess (20:06:25)
do you have anymore math counts promblems
rrusczyk (20:06:39)
Not tonight.
mathquests (20:06:49)
Are there hw and assignments for the MC series?
rrusczyk (20:07:17)
There are message board questions. After each class, we put 10-20 practice problems on the message board for students to discuss.
mathquests (20:07:15)
I mean will u be grading it?
rrusczyk (20:07:40)
We won't be grading the message board, but we will be looking over it in case there are questions from students.
Bart133 (20:07:15)
is there another math counts sessions?
rrusczyk (20:08:07)
Like this one? Not in the near term. We may hold some Math Jams in late February to prepare for states.
Bart133 (20:08:22)
so this is over?
rrusczyk (20:08:45)
We will do the AIME class review in a few minutes
buzzer11 (20:08:23)
the MC series refers the the paid classes, right?
rrusczyk (20:08:50)
Yes.
HoratioK (20:08:32)
What are states?
rrusczyk (20:08:56)
I meant state competitions.
rrusczyk (20:09:16)
Are there any more questions about the MATHCOUNTS Problem Series?
rrusczyk (20:09:42)
I'm going to turn the room over to Naoki Sato to discuss the AIME Problem Series.
nsato (20:09:55)
In the AIME Problem Series, we will be looking at problems that almost all come from the AIME contest.
nsato (20:10:04)
The following problems are taken directly from the AIME Problem Series.
nsato (20:10:13)
nsato (20:10:28)
nsato (20:10:32)
http://www.artofproblemsolving.com/Classes/AIME/Images/1983aime6k14.gif
nsato (20:10:36)
nsato (20:11:14)
nsato (20:11:33)
nsato (20:11:39)
nsato (20:11:47)
When we add these two quantities, which part of the sum is not divisible by 7^2?
HoratioK (20:12:17)
The a*7^1+b*7^0
nsato (20:12:43)
nsato (20:12:53)
What is our final answer?
bpms (20:13:03)
35
HoratioK (20:13:23)
35
nsato (20:13:32)
Our final answer is the remainder when 1162 is divided by 49 which is 35.
bpms (20:13:34)
Could we have used Euler's totient?
nsato (20:14:02)
You could, but the calculations would have taken a lot longer.
nsato (20:14:12)
nsato (20:14:21)
http://www.artofproblemsolving.com/Classes/AIME/Images/1990aime9NoHH.gif
nsato (20:14:28)
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?
bpms (20:14:33)
We could look at smaller cases.
nsato (20:14:43)
We could begin by examining smaller sequences of tosses.
nsato (20:14:47)
One toss outcomes without HH:
H
T
nsato (20:14:52)
Two toss outcomes without HH:
HT
TH
TT
nsato (20:14:59)
In what ways could we toss a coin three times without ending up with HH in the sequence?
HoratioK (20:15:21)
HTH,HTT,THT,TTT
bpms (20:15:21)
TTT, TTH, THT, HTT, HTH
buzzer11 (20:15:32)
HTH, TTT, THT, TTH, HTT
nsato (20:15:54)
Three toss outcomes without HH:
HTH
HTT
THT
TTH
TTT
nsato (20:16:10)
In what ways could we toss a coin four times without ending up with HH in the sequence?
buzzer11 (20:16:37)
TTTT, HTTT, THTT, TTHT, TTTH, THTH, HTHT, HTTH
nsato (20:17:28)
Four toss outcomes without HH:
HTHT
HTTH
HTTT
THTH
THTT
TTHT
TTTH
TTTT
HoratioK (20:17:00)
HTHTH,HTHTT,HTTHT,HTTTT,THTHT,THTTH,THTTT,TTHTH,TTHTT,TTTHT,TTTTH,TTTTT
nsato (20:17:36)
Do we notice anything from examining these smaller cases?
nsato (20:17:59)
What is the sequence of number of flips?
i_like_pie (20:18:20)
2, 3, 5, 8
HoratioK (20:18:17)
2,3,5,8,13
bpms (20:17:53)
Fibonacci
HoratioK (20:18:26)
Fibonacci
nsato (20:18:57)
It looks a lot like Fibonacci. That should tells not only how the pattern continues, but why.
nsato (20:19:10)
How are we constructing each sequence as we add an additional flip?
nsato (20:19:14)
Each flip of n coins either ends in an H or a T. How can we construct new sequences from these possibilities?
nsato (20:19:36)
First we should note that any sequence of n + 1 flips without HH occurring is a sequence of n flips without HH occurring plus one more flip (such that the new sequence does not end in HH).
nsato (20:19:47)
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.
nsato (20:19:53)
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.
nsato (20:20:00)
What does this tells us about the total number of sequences of length n + 1 without an occurrence of HH?
bpms (20:20:01)
Well, if it has a double H than we can add another T or an H at the end. If it doesn't but ends in an H we add another H
nsato (20:20:17)
nsato (20:20:32)
Where can we go from here?
nsato (20:21:04)
nsato (20:21:54)
nsato (20:21:58)
How can we use these facts to help us solve the problem?
HoratioK (20:20:56)
2,3,5,8,13,21,34,55,89,[b]144[/b]
nsato (20:22:17)
bpms (20:22:18)
We can find the 11th fibonacci number
nsato (20:22:59)
We can now say that i/j = 144/1024 = 9/64, so i + j = 73.
nsato (20:23:04)
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.
nsato (20:23:29)
Are there any questions about the AIME problem series>
nsato (20:23:31)
?
buzzer11 (20:24:01)
Are they normally for high schoolers?
nsato (20:24:40)
The AIME problem series is directed at students preparing for the AIME, so yes.
jds4prez_2 (20:24:17)
is 73 the right answer?
nsato (20:24:46)
Yes.
nsato (20:25:43)
Thanks for coming. That's it for tonight's math jam.
