4/28 Exam: Putnam 2008 Part B

This exam was somewhat problematic, in the interest of having to do other work, and a lack of concentration, I had to curtail it a bit. More importantly, I am having a lot of trouble grading myself. I only fully solved one problem, but I have what is almost complete work for two others, and I'm not really sure how much points I would get. (For the second problem, I am not sure what extent of rigour I need, for the third, I have a solution I am pretty confident works but it does not appear among the many official solutions, and is seemingly less complicated). I will have to talk this over both with Mr. Kirk, (just to provide a second opinion), and with someone who knows the competition grading process reasonably well, so that I may get an accurate idea of my score.

At worst (if I get one point for each of those problems), I get a 12, which gives me about a 24 or something for both parts. The cutoff for top 500 for this exam is around a 22, so this isn't terrible.

In the very best case, I would have probably gotten top 200. (This is 9 points for each problem, giving me a score of around 40). But I should probably not expect this.

Here is the one problem I solved completely:



Show that every positive rational number can be written
as a quotient of products of factorials of (not necessarily
distinct) primes.


For example, 10/9=(2!*5!)/(3!*3!*3!).
Recall that n! (n factorial) is 1*2*3*..n.

To prove this for all rational numbers, I actually need only prove it for prime numbers.

Any rational number is a product of numbers of the form p/q or 1/q, where p and q are prime, just split the numerator and denominator into their prime factorizations.

If I have a quotient representation for p, I have it for 1/p, by just taking the reciprocal of the representation. Similarly, I have representation for p and q, I have one for pq, by multiplying the representations. So we can generate all products of the form p/q, if we have all the primes.

We will prove that we can get all the primes by induction on the n-th prime number.

Base case 2=2!

Induction step: Assume it holds true for the 1st through nth prime numbers. Consider the n+1th, prime number, p_n+1. Take (p_n+1)!=(p_n+1)*[(p_n) - 1]!
Take the prime factorization of p_n!, it only has primes from 2 to p_n, (no larger primes can be represented in the factorial), but we have quotient representations for each of these primes, so we have a quotient representation for [(p_n) - 1]!, so we have one for 1/[(p_n) - 1]!, so we have one for (p_n+1)!/[(p_n) - 1]!, (as (p_n+1)! is the factorial of a prime). So we have a representation for p_n+1, and we are done.

Response to Comfort Zone Article

We were tasked to read and respond to this article in class:

For the most part, I disagree with this article. The old adage of "going out of your comfort zone" seems to me trite and overused. Most of the time it merely exposes you to some sort of pointless suffering. If I decided to stab myself with a knife, I would definitely be going out of my comfort zone! However, stabbing oneself is generally not considered a positive experience, or one that contributes to growth. Thus we need to reexamine the idea that going out of one's comfort zone is always a good thing. (I do mathematics, for me, a counterexample, no matter how silly, is a counterexample). It is not always productive, to go out of one's comfort zone for it's own sake, there needs to be another purpose. (Most likely personal growth)

What I think this means is that basically one should do things one believes to be good for oneself, which is a somewhat (read: very) empty statement, but it does not make the mistake of conflating growth and discomfort, when one can both have comfortable growth, and discomfort without growth.

Research Entry

With my project, I guess most of my regular entries are in some capacity "research". (I using print resources to increase my understanding). This is definitely an argument that can be made, but for the most part, what I'm doing is really just "training". So I think it would behoove me to do some actual research. 

I realized I never really explained what exactly the Putnam Exam was, how it is formatted, and how it is graded, so this will be my first research entry. My second will be about other competitions in which I can participate. 

The William Lowell Putnam exam is an annual competition for undergraduate students, administered by the Mathematical Associates  of America. There are two sets of 6 problems, separated by a lunch break. Each problem is graded out of 10 points. The median score is generally somewhere around 2 or 3 points out of 120. 

For each problem, the most common scores are: 0, 10, 9, and 1. A nine is a correct solution with one small mistake. A one is some correct reasoning, leading up to a solution. (Most competitions like this are not very generous with partial credit.)

Awards:

The top 5 finishers are given named Putnam Fellows, and are given $2500 each.

One of them is given a full ride to graduate school at Harvard University.

The next 9  finishers are given $1000 each, and the following 9 are given $250.

The next 50 or so are given Honorable Mentions.

The top 100, 200, and 500 are recorded in some manner.

I also found a lot of statistics from past competitions, which I can use to see where I stack up. 

Assignment from Monday

The assignment from Monday was to blog about some unwillingness or limitation that is preventing me from learning and growing.

I am fortunate to be doing a project that I am very comfortable with. I have basically used the WISE experience to force myself into doing something which I would have done anyway, but most likely failed to follow through.

In the realm of math, I am pretty open to trying new things. I am, however, not comfortable speaking to people I don't know, so I would find personal interviews difficult. However, with this project, I have so many contacts and friends who are experienced with competitive math, that the best people to interview would in fact be people I already know.

The only limitation I can think of is my fear of failure. I am currently in a section of Putnam and Beyond that has really not agreed with me, and under normal circumstances, I would move on to a  different section. However, I don't want to continue doing this. The only way for me to improve is do things that I could not do before. In order to do that, I need to pay even more attention to the problems I feel I can't solve.

4/20 Test/Reflection

So I took the first day of the 2009 Putnam Exam yesterday. It was, as predicted, much harder than the previous exam I took, as that one was many years earlier. I solved one problem, and made some progress on another, but that was about it. I again found it hard to concentrate sometime after the 2-2.5 hour mark. It is probably a good idea to read up on some sort of "concentration exercises". However, I'm really happy I changed my project, and I think forcing myself to do competition math almost daily is definitely a good thing.

Without further ado, here is the problem I solved:


Let f be a real-valued function on the plane such that
for every square ABCD in the plane, f(A) + f(B) +
f(C) +f(D) = 0. Does it follow that f(P) = 0 for all
points P in the plane?

My initial guess was that yes, this is true. (For the following reason: if it weren't I would probably have to find a counterexample, which looks in this case very difficult and sort of annoying. (It's a little more than that, but if you do enough math problems, you get a sort of intuition for this kind of thing).

So I began to look for a "picture", that would confirm this. Basically a figure with a bunch of squares with some common points, I could apply the equation on each square and get some helpful cancellations.

As it turns out, this approach was successful, with the following solution:

Pick a point P in the plane.

Make it the center of some square ABCD.

Label the midpoints of AB, BC, CD, DA, E,F,G,H respectively. (The picture should look like this abysmal MS Paint diagram)

EFGH is a square (this is very easy to verify), as are AEPH, etc. (these are the "quarter squares")

So applying the function to each point in each quarter square and adding them gives:

f(A)+ f(E)+f(P)+f(H) + f(B)+f(E)+f(P)+f(F) + f(C)+f(F)+f(P)+f(G) +F(D)+f(G)+F(P)+f(H)=0, so

f(A)+f(B)+f(C)+f(D)+2(f(E)+f(F)+f(G)+f(H)))+4f(P)=0

but ABCD, and EFGH are squares, so f(A)+f(B)+f(C)+f(D)+2(f(E)+f(F)+f(G)+f(H)))=0

So f(P)=0, and we can make this construction for any point P, so we are done.

Pigeonhole Principle

Apologies for the lack of posts, I have been in Columbia until last Wednesday on a college visit.

Over the past two days, I've worked on the next section of the Methods of Proof chapter in Putnam and Beyond, the Pigeonhole Principle. (Also known as the Box Principle, and many other names). Basically, if you have n holes, and more than n pigeons, at least two pigeons must go in one hole. The primary idea in solving a problem like this is to determine what are the pigeons, and what are the holes.

 I am actually pretty bad at these kind of problems, so I found this section mostly difficult.  I am probably going to continue with it for another day or two. 

Currently, I am definitely lacking in research posts, so I will probably devote most of next week to research.

Here is one of the few problems from the section I have solved. This one is so easy I honestly feel bad about posting it, but I really have nothing better post at this point.

Given 50 distinct positive integers strictly less than 100, prove that some two of

them sum to 99.

Divide the positive integers from 1 to 99 like so:

{1,98}

{2,97}

....

{49,50}

These will be our "holes"

I am assuming if we pick 99, that counts as "summing to 99" otherwise this result is not actually true. (The book's solution seems to agree with me here), so we can basically ignore 99. 

Notice that the remaining integers are all listed here exactly once, there are 49 pairs, and the numbers in a pair sum to 99. If we pick 50 integers (our "pigeons"), by pigeonhole principle, we have to pick 2 from the same pair, which means we have 2 that sum to 99. 

First Test

Today, I took the first day of the 1992 Putnam Exam. I haven't taken a 3 hour math exam in some time, so I had to readjust. I began to lose concentration around the 1.5 hours mark, and was completely useless after an additional hour, so I basically ended up giving up 20 minutes early, because I just couldn't bring myself to do anything more. This will, I hope, improve with time and effort. I took it pretty casually, with a lot of bathroom/water breaks, and I didn't formally write up my solutions. I will be more rigorous with conditions as this process goes on.

The results themselves were actually relatively good. I solved the first and fourth problems, and basically solved the third, but made a stupid in error in getting the final answer. I will post about how Putnam is evaluated later, but I give myself 2.5 problems, which is 25 points. Had I bothered to check that error (which I would have in real competition settings), and written down some preliminary work in the other 3 problems, I would have gotten a 33. Looking at the competition statistics, this is already enough for top 200, (cutoff was 32), despite the fact that I only did the first half of the competition! This is pretty awesome, but unfortunately, it doesn't mean all that much.

The only real conclusion I can draw here is that the competition got significantly more difficult from 1992 to 2013. (In general, competitions get harder as time goes by, because more training materials are developed, and people put a lot more effort into practicing). I should probably concentrate on exams after the year 2000.

Sample Problem:


Prove that f(n) = 1 − n is the only integer-valued function defined on the
integers that satisfies the following conditions:
(i) f(f(n)) = n, for all integers n;
(ii) f(f(n + 2) + 2) = n for all integers n;
(iii) f(0) = 1.

Our approach will be to prove any function, f(n), with these properties must be equal to 1-n.

We are going to use a form of induction, similar to what was described in the previous section.

First, we'll prove it for even positive integers, then odd positive integers.

Since f(f(n))=n, f is it's own inverse, so
applying i) to ii), we get:
f(n+2)+2=f(n)

We are now going to use induction, except adding 2 instead of 1, to prove the statement for the even numbers.
Base case:
f(0)=1=1-0

if f(n)=1-n
f(n+2)=f(n)-2=1-n-2=1-(n+2)
So it is true for 0, therefore it is true for 2,4,etc.

Applying i) to iii), we get f(1)=0, so we can make the same argument for odd positive  integers. (f(f(0)=f(1))

For negative integers, note that when n is positive f(n+1)=1-(n+1)=-n, so f(-n)=f(f(n+1))=n+1=1-(-n), so it is true for negative integers, and we are done.

Update for 4/13: Induction

On Thursday and Friday, I did problems from the second section of Putnam and Beyond, induction. The essence of a proof by induction is the following:

You want to show a statement is true for all positive integers n. (Or nonnegative integers, or integers starting from 3, etc.)

You first show the statement is true for 1 (or whatever you are starting with, this is called the base case), and then show if it is true for some n, it is true for n+1. Then, since it is true for 1, it is true for 2, and 3, and so on. 

Easy example: Prove the sum of the first n odd integers is n^2. 

Base case: n=1, 1^2=1, this is true.

Induction step:

If 1+3+5+...2n-1=n^2 for some n, let us add the next odd number, 2n+1, to both sides, so

1+3+5+...+2n-1+2n+1=n^2 + 2n +1 

but n^2+2n+1 is precisely (n+1)^2, so the statement is true for n+1.

As with the previous section, this is a technique I am very familiar with, but I just wanted to do the problems. I found the problems in this section generally not too difficult, because the way to start is generally clear. (Use induction). I find that working from this book, and making more concrete plans, gives me a much better work ethic, because I have to write a post for each section.

Here is an example from the text that is not quite as easy. 

Prove that for any positive integer n ≥ 2 there is a positive integer m that can be

written simultaneously as a sum of 2, 3, . . . , n squares of nonzero integers.

We will induct on n, as before:

base case: n=2

m=5 works, as

4=1^2 + 2^2

Induction step: so there is an integer m, such that for some n, 

m is expressible as the sum of 2,3..., n squares of integers. We would like to construct an integer m2 such that it is also the sum of n+1 squares of integers. Our first instinct is, naturally, to add a square to m. This gives us a number that is expressible as a sum of 3,4,...n+1 squares, which is almost what we want. So we would also like it to be expressible as a sum of 2 squares. So if

m2=m+c^2

m=a^2 + b^2,

so m2=a^2 + b^2 + c^2  We would like to pick c, such that we can "collapse" this into two squares.  However, this is easy, pick c so that a and c form the two legs of a right triangle. (There is an easy algorithm to generate all integer valued Pythagorean triples, I will talk about in separate post because there is a very nice way to find it)

So a^2 + c^2 = d^2, so m=d^2+b^2, so m is expressible as a sum of 2 squares, so we are done. 

(Note, if a=1, we can't make a triple, so we will use b instead, if b=1, then m=2, but 2 only works as a choice of m for n=2, and we can pick m=5 instead)

Finalized Schedule

So I have obtained a copy of the book  Putnam and Beyond by Razvan Gelca and Titu Andreescu. It is a book that teaches a large amount of undergraduate mathematics, primarily for the purpose of preparing for competitions such as the Putnam competition. My tentative plan is to work through this book during the week, and take "tests" on weekends. (A test would be a complete competition of some kind).

The book gives the advice:


If you are a Putnam competitor, then as you go on with the study of the book try
your hand at the true Putnam problems (which have been published in three excellent
volumes). Identify your weaknesses and insist on those chapters of Putnam and Beyond.
Every once in a while, for a problem that you solved, write down the solution in detail,
then compare it to the one given at the end of the book. It is very important that your
solutions be correct, structured, convincing, and easy to follow.

In keeping with that, I will use my "tests" to determine where I am weak, and what areas I am to focus on more.

I began the book in the beginning (it seemed like a natural place to start), with a section called "techniques of proof". It covered proof by contradiction, proof by induction, etc. (These are all ideas I am familiar with, but the problems they gave were still not easy).

Today, I did some problems from the "'Proof By Contradiction" section, here is one:
(Proof by contradiction is assuming the opposite of what you want to prove, and from there, deriving something that is false, or contradicts your initial assumption)


Every point of three-dimensional space is colored red, green, or blue. Prove that one
of the colors attains all distances, meaning that any positive real number represents
the distance between two points of this color.

Let us assume this is false: That there are positive reals x,y,z such that no two red points are distance x apart, no two blues are distance y apart, and no two greens are distance z apart.


Pick a red point, call the sphere with radius x surrounding it S. All the points in S are blue or green, because otherwise we would have a red point a distance x from the center, which is also red, which would contradict our assumption.

Pick a green point on the sphere. (If there are no green points, all the points on the sphere are blue, so it's easy to find two that are distance y apart)

We find two points on the sphere, Q and R, so PQ=z, PR=z, QR=y. (To see that this is true, anchor a triangle like that to P, and rotate it around P until it's other two points touch the sphere)

If Q or R is green, then it and P make two green points with distance z, which would contradict our initial assumption. So Q and R are both blue, which contradicts our assumption as well, as QR=y, so our assumption is false and our problem is solved.

Training Plan

I don't feel I've been using this break productively enough. And, more importantly, I'm not sure if what I am doing is a good idea. If I just solve random problems, I'm only solving the ones which I find "easy". I don't think this is necessarily productive. I will devote the next few days to determine a sort of "training schedule". Furthermore, it's not really profitable documenting every problem I solve. (the stuff I've posted now are all very simple, as I do more things with more theory behind them, explaining them to a general audience becomes very difficult). I guess I should focus on what steps I am taking, and how I am improving.

Out of the Rut: Partner Read

So I read Jaquan Hurt's blog. Most of his entries are short, which is not in itself bad, as recently , they have increased in frequency. I feel there is a lot of elaboration that he can do, but doesn't. It feels a bit like "diary of a cat". He could definitely use more reflection. Also, he should share some specifics about his work. He is currently writing a story for his game, and I think it would be good for him to show some of the story at least. I am not getting a clear idea of his progress from his journals. He does well in documenting the problems he is having, but often does not volunteer possible solutions.

Modular Arithmetic: A Brief Primer

In order to make the previous post understandable, I will explain some of the machinery behind what I did. It would make it even harder to understand if I included it in the problem itself, so I made a separate post. (If you already understand what I am talking about, please don't read this explanation, as it may cause you to cringe a little)

Modular arithmetic is basically arithmetic with remainders. When we take a number modulo (often shortened to "mod") n, we consider only its remainder when divided by n. We can add, and multiply these remainders in a similar fashion to standard addition and multiplication. Division also works,  so long as you are dividing by something relatively prime to n.  "Equality" is called congruence, and is often denoted by ≡ (a lot of the time people just use =). 

If we are working mod 7:  3+4≡0  5*9≡3 7k≡0 for any integer k

You can think of modular arithmetic as doing arithmetic on a clock, except with n hours. 

The last n digits of a number is equivalent to taking that number mod 10^n.

It is often important in contest problems to compute a^k (mod n), to that end, there are some important theorems:

Fermat's Little Theorem:

a^p≡a (mod p)

alternatively a^p-1≡1 (mod p), for a relatively prime to p.

Proof: Consider the numbers a, 2a, 3a, ... (p-1)a.

Mod p, they are congruent to 1,2,...(p-1) in some order, as they are all distinct, and nonzero, and there are only p-1 nonzero remaidners mod p.  (They are nonzero because a is not congruent to p, and p is prime, so ab can't be a multiple of p if neither a nor b is)
(They are distinct because we can divide out by a)

So if we multiply them all (mod p), we get (p-1)!,
so (a^(p-1))(p-1)!≡(p-1)! (mod p)

We can divide out (p-1)!, concluding our proof. 

(The first statement of the theorem includes the case a≡0, but this is trivial, as 0^p is obviously 0)

But what happens when we are not using a prime?

The theorem does not remain true.

Mod 6, 2^5≡2, which is obviously not 1. 

The issue comes from the fact that 2 is not relatively prime to 6, so 2*n is always 6k+2w, so it can only be congruent to 2, 4, or 0 mod 6. 

However, we can make a revision of the theorem, to correct for this. This is called Euler's theorem, and is the one I used in the previous post. 

Let phi(n) be the number of numbers less than n that are relatively prime to n.

a^phi(n)≡1 (mod n)

This is true by basically the same reasoning as the previous theorem, just list all the numbers relatively prime to n. (there are phi(n)) of them.