Concluding Remarks: What's Next?

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).

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.

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. 

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.

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.

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!

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.

Putnam 2010: Day 1

I took the first part of the Putnam 2010 exam yesterday, it did not go well. I actually liked most of the problems that day, and probably could have gotten three of them. I'm pretty sure I solved only one. (I'm trying to check a solution for a second problem at the moment). For most of the other problems I attempted, I was starting on some incorrect premise, which kind of threw me off. I guess what I should take away from this is that I need to be more careful.

So, here is the problem I did solve, it's actually really easy, and didn't take very long:


A1 Given a positive integer n, what is the largest k such
that the numbers 1,2, . . . , n can be put into k boxes so
that the sum of the numbers in each box is the same?
[When n = 8, the example {1,2,3,6},{4,8},{5,7}
shows that the largest k is at least 3.]

The answer is floor((n+1)/2) (floor(x) denotes the greatest integer smaller than x).
The reasoning is as follows:
If you have a k larger than that, you must have at least 2 boxes with a single number in them, since all the numbers are distinct, then the sums of the numbers in those two boxes are different. (To see this, if only one box has a single number, and each other box has at least two numbers, you get a total number of numbers larger than n).


To show that it's achievable, note that if n is even floor((n+1)/2)
=n/2. So we can just pair the numbers: (1,n), (2,n-1)..., so they all have sum n+1, and put one pair in each box.
With n odd, floor((n+1)/2) becomes (n+1)/2. So we can have one box with just (n), along with the pairs (1,n-1) (2,n-2), etc, all of which sum to n.

Mental Update: What am I doing?

Things have changed from when I was responding to the happiness article. I am definitely not in a state of flow. The past 3 sections on which I am working (Pigeonhole, Extremes, Invariance) have actually proven mostly intractable for me. I don't have solutions for most of the problems in each section. I definitely need to spend more time on this project. I don't think I've put enough effort these past week. This coming week, I have to prepare for Cornell finals, and also submit a very lengthy independent project for one of my classes, which is largely the reason for my not having done a Putnam exam today. However, I do not intend to shortchange myself, and I will therefore, on top of everything else, take a Putnam exam sometime in the middle of this week, and, somehow, spend more time on the other areas of my project.

Invariance

I have been doing various problems from Putnam and Beyond, but I think it's time to post about a new section, Invariants. An invariant is simply something that does not change. I'll give an example of how they can be used to solve contest problems:

67. An ordered triple of numbers is given. It is permitted to perform the following
operation on the triple: to change two of them, say a and b, to (a + b)/
√2 and (a − b)/√2. Is it possible to obtain the triple (1,√2, 1 +√2) from the triple
(2,√2, 1/√2) using this operation?

Let's say we start with a triple (x,y,z), what we can do is find something that does not change when we apply our operation, and if that something is different for our beginning and desired end, then we are done, and we cannot go to that end.

Our invariant turns out to be I(x,y,z)=x^2+y^2+z^2. As
((a + b)/√2)^2 + ((a − b)/√2)^2=(1/2)((a+b)^2-(a-b)^2)=a^2+b^2
Therefore, whichever two numbers from (x,y,z) we pick as our a and b, the sums of their squares are the same.

t I(1,√2, 1 +√2)=6+2√2
and I(2,√2, 1/√2)=6+1/2, which are definitely not the same thing, so we are done.

Happiness Response

So, basically, I haven't done much during the past couple days, because I had to go through a very difficult college decision process. (Say what you will, but I think deciding where I go for the next 4 years takes priority over pretty much anything else). Here is my response to the "Happiness Revisited" handout in class.

1) When do you feel the most happy?
When I am pursuing something I like, on my own terms, and doing well at it.

2) React/respond to article:

I think I largely agree with the idea of optimal experience. I spend a lot of time doing stupid stuff, relaxing, wasting time on the internet. But never during those points have I been as happy as when I've solved a difficult math problem. There is definitely a difference in the feeling you get when you are really actively doing something, than when you are just watching or reading or listening the work (of whatever kind) of someone else. One cannot happy if one does nothing.

3,4,5) I am pretty okay, as it comes to flow. Each section of Putnam and Beyond, and each exam I take, has some easy problems, and some difficult ones, so I can do enough not to be anxious, and still have plenty of challenges to keep me interested. This has basically been the story throughout the course of this project, so I am very happy that I've switched.