My materials are due Friday, however, due to the senior trip, I will submit them on Thursday. I guess that means my project is done. I have no machine built, I have no performance routine perfected. My scores have not improved drastically (it does not help that I've been taking increasingly harder exams).
I don't really have any sense of closure for my project. By no means is my preparation over.
So, what I will do is as follows: I have just conducted two very helpful interviews with people who are very distinguished in math competitions. I have attempted some kind of training regimen for some time. I can use these experiences to come up with a training plan for the summer. Thereby I can end my WISE experience with something concrete, and also continue my obviously incomplete training.
The sources I have gleaned from my interviews are as follows:
Paul Zeitz's The Art and Craft of Problem Solving, I actually own this book and have done some work from it, however, I did not think to use it here.
Yufei Zhao's handouts from the training of the Canadian IMO team. I have seen a few these before, and I am not surprised that they come recommended from both my interviewees. I've actually cited them for some research papers before, but I've never used them for actual training.
I will cite these sources in my works cited as future training materials.
My plan is basically as follows:
Attempt to work through Zeitz, to get general improvement in problem solving-skills. I will try to take practice exams, under exam conditions, every weekend or so.
When I find topics I feel are important, I will work on them via appropriate handouts from Yufei Zhao.
Later in the year, when the Putnam exam approaches, I will switch to Putnam and Beyond, and work on problems in more advanced topics (analysis, abstract algebra, other stuff that isn't really covered in Zeitz).
Wednesday, May 29, 2013
Research Entry: Personal Interview: Forest Tong
Yesterday, I interviewed Forest Tong, who was a USAMO honorable mention (meaning that at one point, he was top 20 in the country in competitive math). He is also the founder of the Ithaca Math Circle, an organization of which I was formerly a part. I asked him the same questions as I asked Ofer, hoping to get a different perspective. Forest is currently a student at MIT.
I: What contests did you participate in?
F: Let's see: AMC, AIME, USA(J)MO, ARML, NY(S)ML, Purple Comet, PUMaC, HMMT, MAML, OMO, Mandelbrot, that should be it...
I: What were your primary training resources for each one?
F: For specific contest training, I would just do past tests and look over the solutions. For getting better at problem-solving in general, I read through and did almost all the problems in Paul Zeitz's Art and Craft of Problem-Solving, which by the way is one of the best books ever written. I also used the AoPS series and classes (WOOT and Olympiad Geometry), and occasionally random handouts on the internet like Yufei Zhao's.
I: How much did you practice for each competition?
F:. I did a lot of AMC, AIME, and USAMO practice tests -- my best estimate would be around 20 AMC's, 10 AIME's, and 10 USAMO's, not including WOOT practice. But the majority of my practice time was spent doing problems in Zeitz. I aimed to spend about an hour a day on problem-solving, even in little chunks of time like while on the bus in the morning.
I: Do you have any general advice for me?
F: Paul Zeitz. No seriously, the first couple of chapters of his book are the best problem-solving advice I've ever encountered.
I: In particular, what are the differences between succeeding in the
Putnam exam vs more "traditional" Olympiads such as the USAMO, IMO,etc?
I: What other options do I have for math competitions in college other than
Putnam and International Math Contest?
F:Putnam is a lot about speed -- you only get half an hour for each problem, I think. The problems often involve only one trick, and can sometimes be pretty contrived. I generally like USAMO problems better, though I have no idea what the writers have been doing in recent years.
F: What's the International Math Contest? I haven't heard of people doing any competitions in college other than Putnam. At MIT, problem-solvers tend to turn to things like the Mystery Hunt.
I: What contests did you participate in?
F: Let's see: AMC, AIME, USA(J)MO, ARML, NY(S)ML, Purple Comet, PUMaC, HMMT, MAML, OMO, Mandelbrot, that should be it...
I: What were your primary training resources for each one?
F: For specific contest training, I would just do past tests and look over the solutions. For getting better at problem-solving in general, I read through and did almost all the problems in Paul Zeitz's Art and Craft of Problem-Solving, which by the way is one of the best books ever written. I also used the AoPS series and classes (WOOT and Olympiad Geometry), and occasionally random handouts on the internet like Yufei Zhao's.
I: How much did you practice for each competition?
F:. I did a lot of AMC, AIME, and USAMO practice tests -- my best estimate would be around 20 AMC's, 10 AIME's, and 10 USAMO's, not including WOOT practice. But the majority of my practice time was spent doing problems in Zeitz. I aimed to spend about an hour a day on problem-solving, even in little chunks of time like while on the bus in the morning.
I: Do you have any general advice for me?
F: Paul Zeitz. No seriously, the first couple of chapters of his book are the best problem-solving advice I've ever encountered.
I: In particular, what are the differences between succeeding in the
Putnam exam vs more "traditional" Olympiads such as the USAMO, IMO,etc?
I: What other options do I have for math competitions in college other than
Putnam and International Math Contest?
F:Putnam is a lot about speed -- you only get half an hour for each problem, I think. The problems often involve only one trick, and can sometimes be pretty contrived. I generally like USAMO problems better, though I have no idea what the writers have been doing in recent years.
F: What's the International Math Contest? I haven't heard of people doing any competitions in college other than Putnam. At MIT, problem-solvers tend to turn to things like the Mystery Hunt.
Monday, May 27, 2013
Research Entry: Personal Interview: Ofer Grossman
Today I interviewed Ofer Grossman, a friend of mine with many impressive achievements in mathematics contests. (Honorable Mention at the International Mathematical Olympiad, Honorable Mention at the United States of America Junior Mathematical Olympiad, top 500 in Putnam, and winner of the Rochester Olympiad)
Here is the transcript of the interview:
It has been edited to only the information necessary, no formalities.
I: What contests did you participate in?
O: I participated in the International Mathematical Olympiad, the United States of America Junior Mathematical Olympad, Putnam, the United States of America Mathematical Olympiad, and many competitions in Israel, including national olympiads and team selection tests for the IMO.
I: What were your primary training resources for each one?
O: In general, I did practice competitions. I also used Paul Zeitz's book, the Art and Craft of Problem Solving, as well as Yufei Zhao's handouts to the Canadian IMO team.
I: How much did you practice for each competition?
O: About 1000 hours in total.I: Do you have any general advice for me?
O: You should really focus on problems you cannot solve, and I'm not sure how to explain this, don't solve them, but in a satisfying way.
I: What does that even mean?
O: Basically, try to make very significant progress on them, before eventually looking at a solution, don't just give up.
I: In particular, what are the differences between succeeding in the
Putnam exam vs more "traditional" Olympiads such as the USAMO, IMO,
etc?
O: It's pretty similar, Putnam obviously incorporates some calculus and other more advanced topics, but you know all the math necessary, so it's basically the same. I find that Putnam solutions are often less "pretty" than USAMO ones.
I: What other options do I have for math competitions in college other than
Putnam and International Math Contest?
O: There are always some kind of local Olympiads. Also, another good thing you can do is write contest problems for local competitions.
Tomorrow, I will interview another contact of mine, with essentially the same questions, and compare results.
Here is the transcript of the interview:
It has been edited to only the information necessary, no formalities.
I: What contests did you participate in?
O: I participated in the International Mathematical Olympiad, the United States of America Junior Mathematical Olympad, Putnam, the United States of America Mathematical Olympiad, and many competitions in Israel, including national olympiads and team selection tests for the IMO.
I: What were your primary training resources for each one?
O: In general, I did practice competitions. I also used Paul Zeitz's book, the Art and Craft of Problem Solving, as well as Yufei Zhao's handouts to the Canadian IMO team.
I: How much did you practice for each competition?
O: About 1000 hours in total.I: Do you have any general advice for me?
O: You should really focus on problems you cannot solve, and I'm not sure how to explain this, don't solve them, but in a satisfying way.
I: What does that even mean?
O: Basically, try to make very significant progress on them, before eventually looking at a solution, don't just give up.
I: In particular, what are the differences between succeeding in the
Putnam exam vs more "traditional" Olympiads such as the USAMO, IMO,
etc?
O: It's pretty similar, Putnam obviously incorporates some calculus and other more advanced topics, but you know all the math necessary, so it's basically the same. I find that Putnam solutions are often less "pretty" than USAMO ones.
I: What other options do I have for math competitions in college other than
Putnam and International Math Contest?
O: There are always some kind of local Olympiads. Also, another good thing you can do is write contest problems for local competitions.
Tomorrow, I will interview another contact of mine, with essentially the same questions, and compare results.
Tuesday, May 21, 2013
What my presentation will be like:
I do not have a product to show, I don't have super tangible evidence of growth. Performance on an individual exam is pretty variable, and my sample size is not very large. I basic "what I did" presentation will turn out pretty uninteresting, however I frame it.
However, I have an idea. I want to present some problems. These problems will be very simple, in the sense that one does not need background to solve them. However, they will not be easy. Some of them will be ones already discussed here. Others, I can find elsewhere.
The purpose of doing this is to give viewers a concrete idea of what I've been doing. And, furthermore, to hopefully convince at least one of them, that math isn't limited to the boring drivel that they probably learned in school. That math can be interesting, fun, and engaging.
However, I have an idea. I want to present some problems. These problems will be very simple, in the sense that one does not need background to solve them. However, they will not be easy. Some of them will be ones already discussed here. Others, I can find elsewhere.
The purpose of doing this is to give viewers a concrete idea of what I've been doing. And, furthermore, to hopefully convince at least one of them, that math isn't limited to the boring drivel that they probably learned in school. That math can be interesting, fun, and engaging.
Sunday, May 19, 2013
Mersenne and Fermat Primes
The material we discussed in the previous entry actually prepares the reader very nicely for a discussion of Fermat and Mersenne primes.
Mersenne primes are primes of the form 2^n - 1.
Fermat primes are primes of the form 2^n + 1.
We can show very easily that if 2^n-1 is prime, n must also be prime. As otherwise, if n=ab, 2^a -1 divides 2^n - 1.
Similarly, if 2^n + 1 is a prime, n must be a power of 2, otherwise if n=(2^m)(2k+1), we have that (2^(2^m) + 1) divides 2^n + 1.
Mersenne primes are notable partially because they are easier to test for "prime-ness" than other numbers, the largest known prime is currently a Mersenne prime (The exponent is 57,885,161). , and they are also used in cryptography, in the "Mersenne Twister" pseudorandom number generator. It is conjectured that there are infinitely Mersenne primes, but this has not yet been proven.
Fermat primes are somewhat more enigmatic, as Fermat conjectured that for n=2^k, for any k, one would get a prime number. However, this conjecture was believed to result from a computational error and was handily refuted by Euler, who showed that k=5 gives a composite number. We actually know no Fermat primes other than k=0,1,2,3,4.
There are plenty of very interesting open questions in mathematics regarding both Fermat and Mersenne primes.
Mersenne primes are primes of the form 2^n - 1.
Fermat primes are primes of the form 2^n + 1.
We can show very easily that if 2^n-1 is prime, n must also be prime. As otherwise, if n=ab, 2^a -1 divides 2^n - 1.
Similarly, if 2^n + 1 is a prime, n must be a power of 2, otherwise if n=(2^m)(2k+1), we have that (2^(2^m) + 1) divides 2^n + 1.
Mersenne primes are notable partially because they are easier to test for "prime-ness" than other numbers, the largest known prime is currently a Mersenne prime (The exponent is 57,885,161). , and they are also used in cryptography, in the "Mersenne Twister" pseudorandom number generator. It is conjectured that there are infinitely Mersenne primes, but this has not yet been proven.
Fermat primes are somewhat more enigmatic, as Fermat conjectured that for n=2^k, for any k, one would get a prime number. However, this conjecture was believed to result from a computational error and was handily refuted by Euler, who showed that k=5 gives a composite number. We actually know no Fermat primes other than k=0,1,2,3,4.
There are plenty of very interesting open questions in mathematics regarding both Fermat and Mersenne primes.
Algebra: Factoring (a^n - b^n)
Now that finals are over, I can resume serious work on this project.
I moved to the Algebra section of Putnam & Beyond, because I was now interested in something more than heuristics.
Something that comes up very often in contest problems is the factorization of a^n-1 and a^n+1.
It is easy to see that a^n -1= (a-1)(1+ a + ...a^(n-1))
And similarly, if n is odd, a^n + 1 =(a+1)(1 - a +a^2 - ... +a^(n-1)).
If n=q*p, we can replace a with a^p or a^q, to get some different identities.
So we basically get that if p divides n, then a^p -1 divides a^n - 1.
Looking at this from a number theoretic perspective, we have the following result:
Theorem: Lifting Exponent Lemma
vp(x^n-y^n)=vp(x-y)+vp(n)
For x,y, integers such that p does not divide x or y, but divides x-y.
vp(x) is called the p-adic valuation of x, and is the largest k such that p^k divides x.
(e.g. v3(18)=2)
The proof of this theorem is a bit complicated, and I will not include it here.
Also, the solutions to most of these problems are not really supposed to involve this theorem, but it is a result I know, so I will use it.
Problem:
Show that for an odd integer n ≥ 5,
(nC0)5^(n-1)-(nC1)5^(n-2)+(nC2)5^(n-3)....+(nCn-1)
is not a prime number.
Recall that (a+b)^n=(nC0)a^n + (nC1)(b(a^(n-1)) +... (nCn)b^n.
Thus our expression is equivalent to:
(((5-1)^n)/5)+(1/5)=(4^n+1)/5
So we now just need to show (4^n+1)/5 is not prime.
For any n>5, pick some p dividing n. By Lifting the Exponent, vp(4^n+1)=vp(5)+vp(n)>0.
So, p|(4^n +1), and, since p is not 5, dividing by 5 does not change this fact.
(If p is 5, then we have v5(5)+v5(n)>1, so when we divide by 5, we reduce the exponent of 5 by 1, so we still get something nonzero)
So if p divides n, p divides (4^n+1)/5, to show (4^n+1)/5, we need to show it must have another divisor, however this is obvious, as (4^n+1)/5 > n>=p, so (4^n+1)/5 is not equal to p, and thus must have another divisor.
Problem: Let a and b be coprime integers greater than 1. Prove that for no n ≥ 0 is a^2n +b^2n
divisible by a + b.
Note that (a+b) divides a^2n-b^2n. (a^n-b^n)(a^n+b^n), if n is even, then (a^2-b^2) divides (a^n-b^n), and (a+b) divides (a^2 - b^2). If n is odd, then (a+b) divides (a^n+b^n).
Assume for the sake of contradiction that for some n, a^2n +b^2n is
divisible by a + b.
Since (a+b) also divides a^2n-b^2n, it divides their difference, 2b^2n.
However, this is impossible, as (a+b) is coprime to b, so we must have (a+b)=2, which cannot happen as a,b>1!
I moved to the Algebra section of Putnam & Beyond, because I was now interested in something more than heuristics.
Something that comes up very often in contest problems is the factorization of a^n-1 and a^n+1.
It is easy to see that a^n -1= (a-1)(1+ a + ...a^(n-1))
And similarly, if n is odd, a^n + 1 =(a+1)(1 - a +a^2 - ... +a^(n-1)).
If n=q*p, we can replace a with a^p or a^q, to get some different identities.
So we basically get that if p divides n, then a^p -1 divides a^n - 1.
Looking at this from a number theoretic perspective, we have the following result:
Theorem: Lifting Exponent Lemma
vp(x^n-y^n)=vp(x-y)+vp(n)
For x,y, integers such that p does not divide x or y, but divides x-y.
vp(x) is called the p-adic valuation of x, and is the largest k such that p^k divides x.
(e.g. v3(18)=2)
The proof of this theorem is a bit complicated, and I will not include it here.
Also, the solutions to most of these problems are not really supposed to involve this theorem, but it is a result I know, so I will use it.
Problem:
Show that for an odd integer n ≥ 5,
(nC0)5^(n-1)-(nC1)5^(n-2)+(nC2)5^(n-3)....+(nCn-1)
is not a prime number.
Recall that (a+b)^n=(nC0)a^n + (nC1)(b(a^(n-1)) +... (nCn)b^n.
Thus our expression is equivalent to:
(((5-1)^n)/5)+(1/5)=(4^n+1)/5
So we now just need to show (4^n+1)/5 is not prime.
For any n>5, pick some p dividing n. By Lifting the Exponent, vp(4^n+1)=vp(5)+vp(n)>0.
So, p|(4^n +1), and, since p is not 5, dividing by 5 does not change this fact.
(If p is 5, then we have v5(5)+v5(n)>1, so when we divide by 5, we reduce the exponent of 5 by 1, so we still get something nonzero)
So if p divides n, p divides (4^n+1)/5, to show (4^n+1)/5, we need to show it must have another divisor, however this is obvious, as (4^n+1)/5 > n>=p, so (4^n+1)/5 is not equal to p, and thus must have another divisor.
Problem: Let a and b be coprime integers greater than 1. Prove that for no n ≥ 0 is a^2n +b^2n
divisible by a + b.
Note that (a+b) divides a^2n-b^2n. (a^n-b^n)(a^n+b^n), if n is even, then (a^2-b^2) divides (a^n-b^n), and (a+b) divides (a^2 - b^2). If n is odd, then (a+b) divides (a^n+b^n).
Assume for the sake of contradiction that for some n, a^2n +b^2n is
divisible by a + b.
Since (a+b) also divides a^2n-b^2n, it divides their difference, 2b^2n.
However, this is impossible, as (a+b) is coprime to b, so we must have (a+b)=2, which cannot happen as a,b>1!
Sunday, May 12, 2013
Putnam 2010: Part 2
Today, I took the second part of the 2010 Putnam. This part was actually a lot harder than previous one, so I'm not surprised I only got one problem here as well. My solutions plus preliminary work put my score at maybe a 24-25, which is actually outside the top 500 for this exam, which is quite dismal.
I am going to chalk it up to my not thinking straight, coupled with some stress due to upcoming exams.
Given that A, B, and C are noncollinear points in the
plane with integer coordinates such that the distances
AB, AC, and BC are integers, what is the smallest
possible value of AB?
For convenience, let A be (0,0). (If you have a triangle that satisfies the statements, you can translate it any of its points to the origin, as you are subtracting integers from all the coordinates)
After some experimentation, I got a value of 3. (Achieved by B=(0,3), C=(4,0), or, if that's too mainstream for you, (10,24)).
I will now proceed to prove that this is as small as you can get, i.e. that AB=1 and AB=2 result in some ridiculous things.
The only way we can get AB=1 or AB=2, is if B=(0,1) or (0,2) (we can switch x and y coordinates, or replace them with negatives, but this can really just be fixed by flipping or switching our axes, so we don't really care), this is true because if B is not on the y-axis, then it has points (x,y), such that x^2 + y^2=1 or 4, and x,y are integers, which obviously cannot happen without one of them being 0.
If AB=1, the B=(0,1), let C be the point (x, y+1). Since AC is an integer, we have that x^2 + (y+1)^2=d^2 (by the Euclidean distance formula) Similarly, since BC is an integer, we have x^2 + y^2=c^2, so we get d^2=c^2+2y+1. However, y<c*, and (c+1)^2=c^2+2c+1>c^2+2y+1, so d^2 is between c^2 and (c+1)^2, so it cannot be the square of an integer. Thus we have a contradiction and AB cannot be 1.
if AB=2, then we do the same thing, except call C (x, y+2).
Using similar, equations, we get d^2=c^2+4y+4. However, y<c, and (c+2)^2=c^2+4c+4, so c^2<d^2<(c+2)^2, so d^2=(c+1)^2, as d^2 is the square of an integer. So, 4y+4=2c+1, which is false because the left hand side is even (multiple of 4), and the right hand side is odd (one plus a multiple of 2). Again, we reach a contradiction. So AB cannot be 1 or 2, and thus has smallest value 3.
*y<c because x is not equal to 0, and x^2+y^2=c^2. If x was 0, then both B and C would be on the y-axis, and then A,B,C would be co-linear.
I am going to chalk it up to my not thinking straight, coupled with some stress due to upcoming exams.
Given that A, B, and C are noncollinear points in the
plane with integer coordinates such that the distances
AB, AC, and BC are integers, what is the smallest
possible value of AB?
For convenience, let A be (0,0). (If you have a triangle that satisfies the statements, you can translate it any of its points to the origin, as you are subtracting integers from all the coordinates)
After some experimentation, I got a value of 3. (Achieved by B=(0,3), C=(4,0), or, if that's too mainstream for you, (10,24)).
I will now proceed to prove that this is as small as you can get, i.e. that AB=1 and AB=2 result in some ridiculous things.
The only way we can get AB=1 or AB=2, is if B=(0,1) or (0,2) (we can switch x and y coordinates, or replace them with negatives, but this can really just be fixed by flipping or switching our axes, so we don't really care), this is true because if B is not on the y-axis, then it has points (x,y), such that x^2 + y^2=1 or 4, and x,y are integers, which obviously cannot happen without one of them being 0.
If AB=1, the B=(0,1), let C be the point (x, y+1). Since AC is an integer, we have that x^2 + (y+1)^2=d^2 (by the Euclidean distance formula) Similarly, since BC is an integer, we have x^2 + y^2=c^2, so we get d^2=c^2+2y+1. However, y<c*, and (c+1)^2=c^2+2c+1>c^2+2y+1, so d^2 is between c^2 and (c+1)^2, so it cannot be the square of an integer. Thus we have a contradiction and AB cannot be 1.
if AB=2, then we do the same thing, except call C (x, y+2).
Using similar, equations, we get d^2=c^2+4y+4. However, y<c, and (c+2)^2=c^2+4c+4, so c^2<d^2<(c+2)^2, so d^2=(c+1)^2, as d^2 is the square of an integer. So, 4y+4=2c+1, which is false because the left hand side is even (multiple of 4), and the right hand side is odd (one plus a multiple of 2). Again, we reach a contradiction. So AB cannot be 1 or 2, and thus has smallest value 3.
*y<c because x is not equal to 0, and x^2+y^2=c^2. If x was 0, then both B and C would be on the y-axis, and then A,B,C would be co-linear.
Subscribe to:
Posts (Atom)