| Transcript
for the Math
Jam "Putnam Math Jam"
on Sep 19. |
| Math Jam hosted by ComplexZeta
(Simon Rubinstein-Salzedo ). |
DPatrick (16:59:13)
Greetings and welcome to today's Putnam Math Jam.
DPatrick (16:59:22)
The William Lowell Putnam Mathematics Competition is a contest for undergraduate college students in the US and Canada. The contest consists of 12 questions over 6 hours, with fully-written proofs (like the USAMO). It is held on the first Saturday in December.
DPatrick (16:59:31)
General information about the Putnam Competition can be found at http://math.scu.edu/putnam/index.html.
DPatrick (16:59:44)
Today's Math Jam is being led by Simon Rubinstein-Salzedo, who will appear on your screen as [b]ComplexZeta[/b]. Simon has served as a teaching assistant for a number of AoPS classes. He is currently a student at UC Santa Barbara.
DPatrick (16:59:58)
Simon will lead the discussion, but before I turn the floor over to him I would like to briefly explain our classroom to students who have not previously attended.
DPatrick (17:00:08)
This classroom is moderated. This means that the messages you type will come to the instructor rather than going directly into the room. The instructor may choose some of the messages and questions to share with all of the students.
DPatrick (17:00:21)
Only the instructors have the ability to send private messages in the classroom. Sometimes they will use these to respond to your comments.
DPatrick (17:00:28)
At this time I will turn the floor over to Simon!
ComplexZeta (17:00:33)
Thanks.
ComplexZeta (17:00:36)
Hello everyone!
ComplexZeta (17:00:49)
First of all, does anyone have any questions about the Putnam in general?
Xevarion (16:59:49)
That's December 2 this year
ComplexZeta (17:01:23)
Okay I'm not getting any questions, so let's start with a problem.
ComplexZeta (17:01:25)
ComplexZeta (17:01:48)
What nice features suggest themselves in the problem statement?
ComplexZeta (17:02:07)
Oh first of all, does everyone understand the problem?
MysticTerminator (17:02:15)
A^3 + B^2A = (A^2 + B^2)A, whoa it's what we want to see
Jimmy (17:02:14)
we can multiply A^2 + B^2 by A and B
ComplexZeta (17:02:37)
Right.
ComplexZeta (17:02:48)
So that gives us a lot of terms that we know a bit about.
ComplexZeta (17:02:54)
That is likely to be helpful.
ComplexZeta (17:03:16)
What else?
Xevarion (17:03:19)
(A-B)^3 = A^3 - 3A^2B + 3AB^2 - B^3 = 0
ComplexZeta (17:03:37)
That's not in general true.
ComplexZeta (17:03:46)
Matrices don't commute, so sometimes the terms come out in the wrong order.
MysticTerminator (17:03:47)
you have ABA terms, etc.
ComplexZeta (17:04:18)
But we have a different factorization.
jmerry (17:03:59)
A-B is not zero.
MysticTerminator (17:03:14)
So yes, it is singular, as (A^2 + B^2)A = (A^2 + B^2)B and if it weren't, we could left multiply by its inverse.
ComplexZeta (17:05:06)
ComplexZeta (17:05:48)
ComplexZeta (17:06:03)
But we assumed that that was not the case at the beginning.
ComplexZeta (17:06:12)
Does that make sense?
Jimmy (17:06:20)
yes
FieryHydra (17:06:24)
i guess
ComplexZeta (17:06:37)
Okay next problem then.
ComplexZeta (17:06:39)
ComplexZeta (17:07:25)
There is one way of solving this problem which might be fairly painful:
ComplexZeta (17:07:43)
We can note that no degree can be higher than 2 and then write out a bunch of equations and try to solve them.
ComplexZeta (17:07:51)
It out to work out.
ComplexZeta (17:07:56)
But it's not very nice.
MysticTerminator (17:07:56)
This is sort of weird. I'd first try to see why/why not we can write it as a(x)c(y) but we probably don't have time for that in the MathJam.
ComplexZeta (17:09:07)
Right.
ComplexZeta (17:09:29)
However, the Putnam is a college math contest, so we can feel free to use more advanced tools: linear algebra.
FieryHydra (17:07:20)
Put x=0,1,-1 and see what it looks like
ComplexZeta (17:09:42)
Right.
ComplexZeta (17:10:45)
So that gives us:
ComplexZeta (17:11:01)
ComplexZeta (17:11:03)
and so forth.
ComplexZeta (17:11:17)
ComplexZeta (17:11:46)
We'd like to interpolate these values with only two polynomials. Why doesn't that work?
ComplexZeta (17:12:29)
Remember: linear algebra is our friend.
ComplexZeta (17:12:54)
Any ideas?
Bictor717 (17:13:32)
They don't form a basis
ComplexZeta (17:13:50)
Okay we're on the right track.
ComplexZeta (17:14:26)
Let's step back a bit.
ComplexZeta (17:14:42)
What happens if we try to solve three equations in two variables most of the time/
mdk (17:15:00)
elimination
ComplexZeta (17:15:17)
Okay, but how many solutions do you want?
ComplexZeta (17:15:22)
I mean, how many are there?
MysticTerminator (17:15:46)
zero, usually
ComplexZeta (17:15:52)
Right.
ComplexZeta (17:15:59)
When are there more than zero?
MysticTerminator (17:16:08)
the equations are linearly dependent
ComplexZeta (17:16:14)
Right.
ComplexZeta (17:16:45)
Analogously, we just have to determine whether our equations are linearly dependent or not.
ComplexZeta (17:17:00)
ComplexZeta (17:17:27)
Over the reals or the complexes, that is.
MysticTerminator (17:17:33)
If they are, we can normalize so the coefficient on the first thing is 1. We then see the coefficient on the last polynomial is -1. However, we can't cancel out the x term.
MysticTerminator (17:17:39)
so, no!
ComplexZeta (17:17:52)
Right.
ComplexZeta (17:17:57)
Therefore there are no solutions.
ComplexZeta (17:18:07)
Does that make sense?
MysticTerminator (17:18:24)
er, maybe
FieryHydra (17:18:45)
yes, it makes perfect sense to me now...
ComplexZeta (17:19:12)
There are some details that need to be checked.
ComplexZeta (17:19:16)
But that's the general idea.
ComplexZeta (17:20:28)
Okay let's try another problem.
ComplexZeta (17:20:34)
ComplexZeta (17:20:54)
Does everyone understand the problem?
Kent Merryfield_4 (17:21:12)
Ordered by inclusion?
ComplexZeta (17:21:19)
Yes.
ComplexZeta (17:22:04)
The question is phrased in such a way as to make it appear a bit harder than it really is.
ComplexZeta (17:22:16)
A lot of you probably already know the answer to this question without realizing it.
coachM (17:21:50)
A hint: One countably infinite set is just like
ComplexZeta (17:22:34)
Just like any other, coachM means to say.
ComplexZeta (17:23:12)
Do we know of any method to get any uncountable set from any countable set?
jmerry (17:23:19)
The most familiar totally ordered uncountable set is the real numbers. Can we construct them?
wiP6Tg3y (17:23:24)
No. Each larger subset of Z needs to contain an integer not present in the previous subset of Z, and there are only countably many integers.
ComplexZeta (17:23:46)
Why must there be a previous subset?
ComplexZeta (17:24:20)
If we have a totally ordered chain indexed by the real numbers, there won't be previous elements.
wiP6Tg3y (17:24:15)
The chain is a [i]totally ordered[/i] set of subsets of Z.
ComplexZeta (17:24:30)
The reals are also totally ordered.
ComplexZeta (17:24:38)
But there's no real number right before 1, say.
MysticTerminator (17:24:37)
I don't think we have well-ordering, though.
ComplexZeta (17:24:53)
Exactly. It could be some total order that isn't a well order.
ComplexZeta (17:25:46)
So let's return to jmerry's comment.
ComplexZeta (17:25:55)
Can we construct the real numbers from some countable set?
ComplexZeta (17:26:00)
Do we know a way of doing that?
wiP6Tg3y (17:26:03)
Oops. The chain can be uncountable - Z is equipollent to Q, and the set of Dedekind cuts of Q is equipollent to R.
Xevarion (17:26:07)
the rationals, Dedekind cuts
MysticTerminator (17:26:07)
Dedekind cuts of the rationals.
ComplexZeta (17:26:18)
Exactly.
ComplexZeta (17:26:45)
ComplexZeta (17:27:16)
Whoops.
ComplexZeta (17:27:27)
ComplexZeta (17:27:43)
Xevarion (17:26:14)
then, find a bijection between Z and Q
ComplexZeta (17:28:00)
Exactly.
ComplexZeta (17:28:16)
So, surprisingly, it can be done.
ComplexZeta (17:28:51)
This construction can actually be used to solve quite a few problems.
ComplexZeta (17:29:15)
Here's one: Prove that not every vector space is isomorphic to a dual space of another vector space.
ComplexZeta (17:29:21)
I'll leave that as an exercise.
ComplexZeta (17:29:37)
Next problem.
ComplexZeta (17:29:40)
ComplexZeta (17:29:51)
Does the question make sense?
MysticTerminator (17:29:52)
generating functions?
ComplexZeta (17:30:37)
That's certainly a logical strategy.
ComplexZeta (17:31:04)
ComplexZeta (17:31:15)
ComplexZeta (17:31:29)
What would be our generating functions?
MysticTerminator (17:31:41)
a_1 + a_2 x + a_3 x^2 + ..., b_1 + ...
ComplexZeta (17:32:20)
ComplexZeta (17:32:59)
Let's use MysticTerminator
ComplexZeta (17:33:03)
's generating functions.
ComplexZeta (17:33:21)
ComplexZeta (17:33:31)
Bictor717 (17:34:14)
A(x)B(x)=(1+x+...)/11
ComplexZeta (17:34:41)
What next?
ComplexZeta (17:34:55)
MysticTerminator (17:33:09)
so we want to know if (x^10 + ... + x + 1) factors into two real polynomials of degree 5. Let us be complex?
jmerry (17:35:29)
For this to work, both A and B have to be of degree 5.
MysticTerminator (17:35:11)
look at the roots.
ComplexZeta (17:35:53)
What are the roots?
Xevarion (17:36:18)
the 11th roots of unity except for 1
ComplexZeta (17:36:26)
Right.
ComplexZeta (17:36:48)
ComplexZeta (17:37:02)
Note that they're real polynomials.
MysticTerminator (17:36:56)
complex conjugates - failure
ComplexZeta (17:37:39)
Right -- they must come in complex conjugate pairs. But we have five pairs, so one of them must be split.
ComplexZeta (17:37:43)
Therefore we can't do it.
ComplexZeta (17:38:04)
Next problem.
ComplexZeta (17:38:06)
ComplexZeta (17:38:32)
By square, I mean the lattice points in the interior as well as the boundary.
Kent Merryfield_4 (17:39:25)
A number theory problem - it involves gcd's or other number theory notions.
ComplexZeta (17:39:41)
First of all, which points are blocked?
ComplexZeta (17:40:24)
Can you tell easily if (292,138) is blocked?
MysticTerminator (17:40:37)
gcd >= 2, i.e. not 1 - yes it is
wiP6Tg3y (17:40:38)
A point is blocked iff 1 is not a GCD of its coordinates. (292, 138) is blocked.
ComplexZeta (17:40:46)
Right.
ComplexZeta (17:41:28)
So we're doing a problem dealing with relatively prime integers.
ComplexZeta (17:41:32)
What does that suggest?
ComplexZeta (17:42:20)
Okay let's step back a bit.
ComplexZeta (17:42:31)
Can we find a two by two square of blocked points?
coachM (17:42:50)
We could start by drawing a small table
jmerry (17:42:56)
x-coordinates 20 and 21, y-coordinates 35 and 36
ComplexZeta (17:43:21)
Yes, that's one example.
ComplexZeta (17:43:42)
How did jmerry figure that out?
coachM (17:43:16)
GCD(a, b). The bottom left corner looks like
coachM (17:43:24)
1 2 1 4 1
coachM (17:43:52)
1 1 3 1 1
coachM (17:43:57)
1 2 1 2 1
coachM (17:44:09)
1 1 1 1 1
ComplexZeta (17:44:25)
Eventually I suppose you'll find one.
ComplexZeta (17:44:37)
But you'll have to go pretty far to find 20,21 and 35, 36
ComplexZeta (17:44:56)
(Actually 20, 21 and 14, 15 is smaller, so it will take slightly less time.)
ComplexZeta (17:45:42)
But let's return to jmerry's example. How do you think he figured that out?
ComplexZeta (17:45:56)
I doubt he just guessed until he got there.
ComplexZeta (17:46:40)
Note that 20=2*2*5, 21=3*7, 35=5*7, and 36=2*2*3*3.
ComplexZeta (17:46:53)
So for example 20 and 36 share a factor of 2.
ComplexZeta (17:46:57)
Thus (20,36) is blocked.
Bictor717 (17:46:41)
CRT?
ComplexZeta (17:47:10)
Great.
ComplexZeta (17:47:16)
How does that help us?
ComplexZeta (17:48:20)
Jmerry took the primes 2, 3, 5, 7 and used them to form a 2 by 2 square of blocked points.
ComplexZeta (17:48:46)
There are numbers divisible by 2*5 and 3*7 that differ by one, and there are numbers divisible by 2*3 and 5*7 that differ by one.
ComplexZeta (17:48:59)
That gives us a 2 by 2 blocked square.
ComplexZeta (17:49:06)
How would we construct a 3 by 3 blocked square?
ComplexZeta (17:49:24)
We can do it with the same method.
ComplexZeta (17:49:32)
Does anyone see how?
MysticTerminator (17:50:58)
hmm, can we just take more distinct primes?
ComplexZeta (17:51:13)
Sure.
ComplexZeta (17:51:20)
We can take 9 primes to form a 3 by 3 square.
ComplexZeta (17:51:48)
ComplexZeta (17:52:23)
ComplexZeta (17:52:51)
ComplexZeta (17:53:03)
Together they'll give us a 3 by 3 blocked square.
ComplexZeta (17:53:23)
Xevarion (17:54:04)
just take n^2 distinct primes...
ComplexZeta (17:54:14)
Exactly.
ComplexZeta (17:54:20)
And then we do the same argument once again.
mdk (17:54:16)
take n^2 primes and use chinese remainder theorem?
ComplexZeta (17:54:28)
Yup.
ComplexZeta (17:54:31)
Does that make sense?
mdk (17:54:39)
yes
ComplexZeta (17:55:29)
Do we have time for one more problem?
FieryHydra (17:55:37)
yes
ComplexZeta (17:55:44)
That's the spirit!
ComplexZeta (17:55:53)
ComplexZeta (17:56:15)
Argh. I tihnk I messed that up.
ComplexZeta (17:56:21)
ComplexZeta (17:56:24)
That's better.
ComplexZeta (17:56:44)
Any ideas?
FieryHydra (17:57:04)
put n=2,3 to see is there is a pattern
Jimmy (17:57:05)
try small cases
ComplexZeta (17:57:13)
Okay.
ComplexZeta (17:57:29)
Here's an example:
ComplexZeta (17:57:41)
ComplexZeta (17:58:22)
MysticTerminator (17:57:13)
work with sums of terms of the form a_{i+1} - a_i
ComplexZeta (17:58:53)
Sure, any difference can be expressed as a sum of a bunch of those.
ComplexZeta (17:59:01)
How do you make progress though?
ComplexZeta (17:59:18)
It's not so clear to me.
ComplexZeta (17:59:48)
I suggest working with generating functions again.
ComplexZeta (17:59:59)
Generating functions tend to be good for working with sums and differences of a bunch of things.
ComplexZeta (18:00:24)
ComplexZeta (18:01:09)
ComplexZeta (18:01:12)
But what is that something?
coachM (18:01:15)
It looks like we need to look at
coachM (18:01:42)
A(x) A(x^{-1}) multiplied by a power of x.
Xevarion (18:01:58)
A(x) * A(1/x)
ComplexZeta (18:02:10)
Right.
ComplexZeta (18:02:36)
ComplexZeta (18:03:28)
MysticTerminator (18:03:12)
we want A(x) * A(1/x) = n + (x + ... + x^{C(n, 2)}) + (1/x + 1/x^2 + ... + 1/x^{C(n, 2)}) or something
ComplexZeta (18:03:47)
Yes.
ComplexZeta (18:04:14)
ComplexZeta (18:04:39)
ComplexZeta (18:05:13)
ComplexZeta (18:05:33)
What might we try now?
wiP6Tg3y (18:07:12)
Every integer n>2 has the stated property.
ComplexZeta (18:07:27)
Why do you say that?
ComplexZeta (18:08:41)
Let's turn back to our last expression.
ComplexZeta (18:09:06)
The left side looks easier to work with than the right side, so let's try that first.
ComplexZeta (18:09:21)
MysticTerminator (18:09:59)
0 isn't allowed and 1 doesn't really tell us anything we don't know . . . -1 ?
ComplexZeta (18:10:15)
That seems a reasonable idea.
ComplexZeta (18:10:22)
What does the left side then become?
MysticTerminator (18:10:31)
A(-1)^2 = blah
Bictor717 (18:10:39)
A(-1)^2
ComplexZeta (18:10:51)
Aha!
ComplexZeta (18:10:58)
Something squared.
ComplexZeta (18:11:05)
That seems interesting.
ComplexZeta (18:11:14)
Can we plug in other values to give us squares on the left side?
ComplexZeta (18:11:36)
Negative one alone won't give us enough information to solve the problem.
ComplexZeta (18:12:28)
ComplexZeta (18:13:10)
ComplexZeta (18:13:58)
ComplexZeta (18:14:25)
ComplexZeta (18:15:06)
Jimmy (18:16:16)
2pi
ComplexZeta (18:16:34)
ComplexZeta (18:17:15)
ComplexZeta (18:17:47)
The (simplified) situation we have now is a left side which must be nonnegative and a right side which doesn't seem to have to be.
ComplexZeta (18:18:08)
So perhaps we can force the right side to be negative to give us a contradiction.
mdk (18:18:19)
so what will?
ComplexZeta (18:18:54)
What if we let the numerator of the sine term be negative one?
ComplexZeta (18:19:23)
ComplexZeta (18:19:40)
But then the denominator is a mess.
ComplexZeta (18:20:00)
Ah coachM points out something interesting:
coachM (18:19:24)
Even if we only look at x = -1, we get A(-1)^2=n, so for most n there's no solution.
ComplexZeta (18:20:50)
Can we clean up the denominator by means of some approximation?
ComplexZeta (18:21:37)
Bictor717 (18:21:31)
sin theta is on the order of theta for small theta
ComplexZeta (18:21:58)
ComplexZeta (18:22:27)
If we substitute in that bound, what does the sine term become?
ComplexZeta (18:23:21)
ComplexZeta (18:23:45)
ComplexZeta (18:23:54)
ComplexZeta (18:24:07)
ComplexZeta (18:25:02)
Kent Merryfield (18:25:02)
certainly for all sufficiently large $n,$ whatever ""sufficiently large"" is.
ComplexZeta (18:25:18)
Right.
ComplexZeta (18:25:44)
ComplexZeta (18:26:19)
jmerry (18:26:08)
A different approach: we try to build the list starting with 0 and N. We must add 1, N-2, and 4. This leads to a contradiction, as both 5 and N-5 give duplication as long as n>5
ComplexZeta (18:26:51)
Why must we add 1, N-2, and 4?
ComplexZeta (18:27:29)
Oh I see what you're saying. We need to get N-1, etc.
ComplexZeta (18:27:56)
Okay that's a bit easier :)
ComplexZeta (18:28:23)
So I suppose we should stop here.
ComplexZeta (18:28:34)
Does anyone have any questions?
Bictor717 (18:28:56)
Do you have to explain gen. fcns. when you write up your soln.?
ComplexZeta (18:29:17)
Explain that you're using them, but you don't have to explain what they are.
Bictor717 (18:29:32)
Ok, thanks for everything
ComplexZeta (18:29:41)
You're welcome.
Jimmy (18:29:43)
Ya, thanks for your time
ComplexZeta (18:29:55)
I hope it was enjoyable.
Jimmy (18:30:23)
I think I learned a lot, even though some went over my head.
mdk (18:30:40)
it was, thanks
FieryHydra (18:31:55)
yeah, a lot of it went over my head, but i think i found enough motivation to work harder now! :)
FieryHydra (18:32:12)
thanks ComplexZeta for your time and effort!
ComplexZeta (18:32:17)
That's good.
mdk (18:32:37)
Good night everyone.
MysticTerminator (18:38:27)
general happiness
ComplexZeta (18:38:34)
Is it?
MysticTerminator (18:38:39)
sure, why not?
