| Transcript
for the Math
Jam "AoPS Classes Math Jam"
on Oct 9. |
| Math Jam hosted by nsato
(Naoki Sato ). |
nsato19:36:05
Hello, and welcome to the Intermediate Counting & Probability and Intermediate Number Theory Seminar math jam. Today we'll be discussing what these classes cover and how it works, and answering any questions you may have.
nsato19:36:21
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.
nsato19:36:45
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.
nsato19:36:57
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.
nsato19:37:24
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.
nsato19:37:33
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
nsato19:37:39
nsato19:37:49
This message will look like this when posted in the classroom:
nsato19:37:51
nsato19:38:02
Just remember, if your post uses LaTeX, use the semicolon (;) to begin your post!
nsato19:38:07
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.
nsato19:38:34
First, I'll talk about the Intermediate Counting & Probability class. I'll take all questions at the end.
nsato19:38:50
Intermediate Counting & Probability
nsato19:39:04
The Intermediate Counting & Probability class will cover a variety of powerful counting and probability tools. The topics in the course will include discrete mathematics, including clever one-to-one correspondences, principle of inclusion-exclusion, generating functions, distributions, pigeonhole principle, induction, constructive counting and expectation, combinatorics, recursion, and conditional probability.
nsato19:39:27
The course will be taught by Dave Patrick, who is also the author of the Introduction to Counting & Probability and Intermediate Counting & Probability textbooks (the latter of which will be used in this class; more about this later).
nsato19:39:32
Here is a sample problem:
nsato19:39:36
nsato19:39:49
We're going to do this problem a couple different ways. Are there any suggestions about how to approach it?
nikki19:40:33
casework?
nsato19:40:40
We can try cases. What cases should we consider?
xpmath19:41:26
on a face, diagonally, or internal
LHM19:41:26
On the surface
LHM19:41:26
internal diagonals
nsato19:41:33
Our cases are those sets which are not diagonals, sets which are '2D' diagonals (such as those which are the diagonal of a square), and '3D' diagonals.
nsato19:41:43
nsato19:41:51
nsato19:41:59
nsato19:42:07
So, we start with our first case:
nsato19:42:12
nsato19:42:26
How many are there?
nsato19:43:14
In the direction shown, there are 4 on each level. Therefore, there are 4^2 = 16 with that direction since there are 4 levels.
nsato19:43:24
There are two other directions we could have chosen, examples of which are here in red and blue:
nsato19:43:33
nsato19:43:38
How many are there in each of these directions?
nikki19:44:04
the blue also has 4^2 = 16 ways
krakola4519:44:04
16
phs1945_219:44:04
16 of each
nikki19:44:10
the red also has 4^2 = 16 ways
RollandWu19:44:15
8x6=48
alexhhmun19:44:15
48
nsato19:44:25
There are 4^2 in each of these directions, as well. So our total for the 'not diagonal' case is 3(4^2) = 48.
nsato19:44:30
How about the '2D Diagonal' case?
nsato19:44:34
nsato19:44:39
How can we classify these?
nsato19:45:21
We note that in any given square, there are two of these 2D diagonals:
nsato19:45:28
LHM19:45:31
2 diagonals for each "layer"
nsato19:45:36
How many such squares are there?
LHM19:46:03
12
m1mxl0119:46:16
12
alexhhmun19:46:17
24 2D diagonals
nsato19:46:28
There are 4 of these 'squares' facing in each direction, and there are 3 possible orientations of these groups of squares, so there are 3(4) squares. Thus, for the '2D diagonal' case we have 2*3*4 = 24 4-in-a-row configurations.
nsato19:46:32
What about the 3D case:
nsato19:46:37
nsato19:46:58
How many such diagonals are there?
LHM19:47:21
4
krakola4519:47:21
4
phs1945_219:47:21
4?
nsato19:47:29
There are 4 interior diagonals of the cube, so here we have 4. What is that total?
xpmath19:48:35
48+24+4=76
locke19:48:35
76
nsato19:48:41
nsato19:49:00
That's the orderly casework approach - we teach that general approach in Introduction to Counting. In Intermediate Counting, we learn a slick way to do it.
nsato19:49:06
Now, does anyone see a slick way to do it?
nsato19:49:35
In the Intermediate counting class we will spend a couple days on 1-1 correspondences. What this basically means is to find a relationship between what we want to count and something that's easy to this count.
nsato19:49:45
Sometimes this feels almost like magic. In the course we will talk about how to see these 1-1 correspondences. Here, we have to see something that isn't there. Suppose we take a slightly larger cube:
nsato19:49:53
nsato19:49:59
Our 4x4x4 cube is embedded in a 6x6x6 cube. How can we relate our 4-in-a-rows to the 6x6x6 cube?
nsato19:50:44
Any 4 in the row when extended hits our big cube in two places:
nsato19:50:53
nsato19:50:59
There are four examples in that diagram: notice how when we extend the red 4-in-a-row it hits our big cube in 2 places. And when we extend the blue 4-in-a row it hits the big cube in 2 places, and so on.
nsato19:51:47
Conversely, if we go the other way: start from a point on the big cube and find a 4-in-a-row in the little cube, there's only one way to do it:
nsato19:51:54
nsato19:51:58
Look at the red point. There's only one way to put a line through it to get a 4-in-a-row in the smaller cube. Same for the green point in the upper left corner. Same for the purple point; same for the blue.
nsato19:52:14
So? How does this give us a way to count our 4-in-a-rows?
nsato19:52:49
For every 4-in-a-row, there's a pair of points on the outside of the big cube. For every pair of points on the outside of the big cube, there's a four in a row. Thus, we have what we call a 'one-to-one correspondence' between opposite pairs of points on the outside of the cube and 4-in-a-rows.
nsato19:53:11
Therefore, to count our 4-in-a-rows, we just count the points on the outside of the cube and divide by two. How many points are on the outside of the cube?
nikki19:53:38
6^3 = 216
nsato19:53:44
And what do we do with 6^3 = 216?
nsato19:54:30
nsato19:54:53
Notice that we've completed the problem in two different ways and found the same answer both times, so we're probably right.
nsato19:55:05
But wait, there's more.
nsato19:55:08
Take a look at our two answers:
nsato19:55:13
nsato19:55:17
Why are these the same?
nsato19:56:37
That these are the same is a result of the Binomial Theorem.
nsato19:56:41
nsato19:56:53
We'll use the Binomial Theorem and many other tools to develop all sorts of neat relationship when we talk about combinatorial identities.
nsato19:57:02
Here are a couple more problems that can be solved with clever correspondences:
nsato19:57:06
Define the alternating sum of a set as follows:
nsato19:57:12
List the elements of the set in decreasing order. Take the first number in the list, subtract the second, add the third, subtract the fourth, and so on. Thus, the alternating sum of the set {3,5,11,7} is 11-7+5-3=6.
nsato19:57:24
Find the sum of the alternating sums of all of the subsets of {1,2,3,4,5,6,7,8,9,10}.
nsato19:57:31
And:
nsato19:57:35
Our club has 8 members. We are going to form two committees.
Each person must serve on at least one committee (and may serve on both), and each committee must have at least one member. The two committees are indistinguishable, so the pair of committees {Ajai, Bob}, {Mary} is the same as the pair {Mary}, {Ajai, Bob}. How many ways can we form the committees?
nsato19:58:31
These problems are roughly middle-level difficulty for the course. The example we did was slightly easier than the average problem in the course.
nsato19:58:40
You can find more questions like those we cover in the course by checking out the Post Test for the course here:
nsato19:58:48
Students should have a complete mastery of basic counting (at the level of Introduction to Counting & Probability) before taking this course. Students should also have a solid algebra background through at least algebra II. Students who have completed the Art of Problem Solving Intermediate Algebra and Introduction to Counting & Probability classes should feel comfortable taking this class. (However, students are not required to take these classes before taking Intermediate Counting & Probability.)
nsato19:59:22
The course will meet for 18 weeks on Wednesdays, starting October 31, at 7:30 PM Eastern / 4:30 PM Pacific. (There are no classes on November 21 or Dec 19-Jan 2.) The last class date is March 26. Each class is 90 minutes.
nsato19:59:33
This course will use a textbook in conjunction with the course: our new Introduction to Counting & Probability book. The material covered in the textbook is roughly equivalent to the material covered in the course. You can see the table of contents and an excerpt from the book here:
nsato19:59:41
The book is required for the course. Students will be able to read additional material that complements the lectures, and will have access to a large number of practice problems at varying levels of difficulty. We are recommending that students read the corresponding chapter(s) in the book before each lecture, and attempt some of that chapter's Review and Challenge Problems after each lecture. We also expect to spend some class time answering students' questions about problems from the textbook.
nsato19:59:56
The homework for the class consists of weekly problems that will be posted to the class message board -- for these problems, you do not turn your solutions in, however you may post them to the message board if you like. The class also has three longer problem sets -- one for each 6-week period of the course -- for which you should write up your full solutions and submit them. These solutions will be read, and you will receive detailed feedback.
nsato20:00:37
Now I'll talk about the Intermediate Number Theory Seminar. (I'll take questions about both classes at the end.)
nsato20:00:42
Intermediate Number Theory
nsato20:00:47
The Intermediate Number Theory Seminar is an 8 week course for students who have both a strong foundation in basic number theory and solid algebraic skills. It is recommended that students take the Introductory Number Theory course and Intermediate Algebra course before enrolling, or be confident with the material covered in those classes.
nsato20:00:53
Topics covered in the Intermediate Number Theory Seminar include algebraic methods of problem solving in number theory, base number problems involving algebra, counting, and qualitative problem solving techniques, divisibility and divisor problems involving algebra, Diophantine equations, modular arithmetic with an emphasis on algebraic applications, perfect squares, an introduction to Pell's equations, Fermat's Little Theorem, Euler's Phi Function, and Euler's Theorem.
nsato20:01:12
As with all AoPS classes, the Intermediate Number Theory Seminar will have its own private message board in the AoPS Forum. The Intermediate Number Theory class will include more message board problems per week of class than other AoPS courses to be sure that students get ample practice with the concepts discussed in each lesson.
nsato20:01:25
We will now work a few problems from different days in the class. We will start with an easier class problem and move into harder ones. Unfortunately, we cannot sample some of the most important topics covered in class because it would take too much time developing the background to discuss them here.
nsato20:01:40
nsato20:01:49
How can we approach this problem?
RollandWu20:02:31
factor
nsato20:02:37
nsato20:02:47
How does this factorization help us?
xpmath20:02:54
(x+2)(x+1) must be divisible by 6
nsato20:03:41
We want (x + 1)(x + 2) to be divisible by 6. What conditions does that impose on x?
nsato20:04:26
We can now see that f(s) will always be even because either x + 1 or x + 2 must be even. This examination of the evenness or oddness of the integers is called a "parity" argument.
nsato20:04:49
Our goal now is to find out exactly when f(s) will be a multiple of 3.
nsato20:04:53
When will f(s) be a multiple of 3?
xpmath20:05:29
when x is 2 mod 3 or 1 mod 3
RollandWu20:05:29
one of x+1, x+2 is divisible vy 3
xpmath20:05:33
So, basically, when x is not divisible by 3
nsato20:05:37
f(s) = (s+1)(s+2) will be a multiple of 3 when either s + 1 or s + 2 is a multiple of 3. This is the same thing as saying that f(s) will be a multiple of 3 when s is NOT a multiple of 3.
nsato20:05:40
What is our answer?
xpmath20:06:22
17
nsato20:06:27
We now count the members of S that aren't multiples of 3 and we count a total of 17 of them.
nsato20:07:06
The key to this problem was factoring the function. Once we did that, the actual divisibility arguments were relatively simple.
nsato20:07:11
nsato20:07:14
nsato20:07:27
Where do we start?
nsato20:08:07
We're going to have to dig into the general relationship between any group of digits in base numbers and their values.
nsato20:08:12
nsato20:08:25
What can we say about the digits?
xpmath20:09:01
1 or 0
nsato20:09:08
nsato20:09:10
What else can we do now?
nsato20:09:33
nsato20:09:51
How does representing n by a general group of digits help us?
nsato20:10:12
nsato20:10:18
Now we're getting somewhere!
nsato20:10:20
Er...where would that be?
nsato20:10:48
We can now apply what I like to call the Fundamental Principle of Algebraic Problem Solving -- find two ways to express the same thing and set them equal!
nsato20:10:57
krakola4520:11:01
subtract them
nsato20:11:08
nsato20:11:13
How does this help us?
nsato20:12:00
nsato20:12:10
nsato20:12:22
What else can we say?
nsato20:12:42
What are the possible values of k?
krakola4520:13:26
k<3
xpmath20:13:30
less than 3
nsato20:13:33
nsato20:13:40
What are the solutions?
nsato20:14:38
Checking values in our range we find that n = 0, 5, or 6, so our answer is 3.
nsato20:14:51
The key to this problem was using a sequence of variables to represent the digits of n so that we could use these variables to compare the two different ways we had to express the value of n. Once we did that, we could fall back on our algebraic skills using equations and inequalities.
nsato20:15:14
Are there any questions about the classes?
krakola4520:15:51
are we going to do any more problems
nsato20:16:01
That's it for sample problems; now we're taking questions.
phs1945_220:16:50
if n = 0,5,6 then how did you get 3?
nsato20:17:00
The 3 refers to the number of solutions.
arbelos0820:17:44
how did you get the inequality above to bound
a_0+a_1
nsato20:17:48
We have the equation
nsato20:17:54
nsato20:18:46
All the coefficients of the form 3^k - 2^{k + 1} are positive, and each a_k is 0 or 1.
nsato20:19:08
Hence, we can drop all the terms except the last term, and a_k, to get the bound
nsato20:19:14
phs1945_220:20:14
where did 2 come from?
nsato20:20:27
Each a_k is 0 or 1, so a_0 + a_1 is 0, 1, or 2.
phs1945_220:20:40
on f(s) question.. how are 17 counted?
nsato20:21:35
We saw that f(s) = (s + 1)(s + 2) is divisible by 6 if and only if s is not a multiple of 3. Therefore, we take {0, 1, 2, ..., 25} and take out all the multiples of 3, which are 0, 3, 6, ..., 24.
nsato20:22:59
There are 9, so the answer is 26 - 9 = 17.
LHM20:25:21
If we find the INtroduction class to easy, but this class was really confusing at firrst until you read it all over again, and I have done Algebra, but ALgebra 2, then should I take this class? My school does Geom. right after Algebra.
nsato20:26:43
I would recommend the Intermediate Counting class, mainly because it has a textbook that you can consult in addition to the other materials. And as usual, you may drop the class after two lectures if you still find it too difficult.
phs1945_220:26:53
is there easy way to count multiples of 3 in a set of numbers?
nsato20:27:51
In this case, it was, because they were consecutive. You just have to identify them, and then count, just like counting the number of terms in a set of numbers that are consecutive.
nsato20:28:56
Are there any other questions about the classes?
mathquests20:29:40
will these classes help with AMC 10 or 12
nsato20:30:19
I would say most of the material in these classes are at AIME level, rather than AMC10 or 12. It may help with the hardest problems on the AMC 12.
nsato20:31:08
Thanks for coming to tonight's math jam!
