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.
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.
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.
Sunday, May 5, 2013
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.
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.
Thursday, May 2, 2013
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.
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.
Sunday, April 28, 2013
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.
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.
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.
Wednesday, April 24, 2013
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.
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.
Sunday, April 21, 2013
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.
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.
Saturday, April 20, 2013
Pigeonhole Principle
Apologies for the lack of posts, I have been in Columbia until last Wednesday on a college visit.
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.
Saturday, April 13, 2013
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.
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)
Tuesday, April 9, 2013
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.
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.
Thursday, April 4, 2013
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.
Monday, April 1, 2013
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.
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.
Saturday, March 30, 2013
New Problem (1985 A4)
So I am continuing work on the 1985 Putnam, I recently solved problem A4. Unfortunately, like A1, it was not very hard. I have not yet solved any problem of which I am particularly proud. Ah well, I should keep on working.
Define a sequence {ai} by a1 = 3 and ai+1 = 3^ai for i ≥ 1. Which integers
between 00 and 99 inclusive occur as the last two digits in the decimal expansion of
infinitely many ai?
Okay, starting this problem in a clever way is difficult, so I decided to just compute the first few terms of the sequence, and see what happens.
a1=3
a2=27
a3=3^27 (don't know last digits as yet)
I can perform my operations modulo 100 (looking at the remainder of everything when divided by 100), and just get the last digits. However, the other digits matter when taking 3^ai. It would be really nice for me if they didn't matter. (i.e. 3^100=1 mod 100). I know from Euler's theorem 3^40=1 (mod 100). It would be very nice for me if 3^20 was the same thing. I unfortunately just decided to compute it directly.
3^20=(3^4)^5=81^5=81*81*81^3=61*81^3=61*61*81=21*81=1701=1 (mod 100), so 3^20=1, and therefore 3^100=1^5=1)
So a3=3^27=3^7=81*27=2187=87 (mod 100)
a4=3^87 mod 100
=3^7 mod 100=87.
So after a3, all our ai have last digit 87. So our answer is just 87.
Define a sequence {ai} by a1 = 3 and ai+1 = 3^ai for i ≥ 1. Which integers
between 00 and 99 inclusive occur as the last two digits in the decimal expansion of
infinitely many ai?
Okay, starting this problem in a clever way is difficult, so I decided to just compute the first few terms of the sequence, and see what happens.
a1=3
a2=27
a3=3^27 (don't know last digits as yet)
I can perform my operations modulo 100 (looking at the remainder of everything when divided by 100), and just get the last digits. However, the other digits matter when taking 3^ai. It would be really nice for me if they didn't matter. (i.e. 3^100=1 mod 100). I know from Euler's theorem 3^40=1 (mod 100). It would be very nice for me if 3^20 was the same thing. I unfortunately just decided to compute it directly.
3^20=(3^4)^5=81^5=81*81*81^3=61*81^3=61*61*81=21*81=1701=1 (mod 100), so 3^20=1, and therefore 3^100=1^5=1)
So a3=3^27=3^7=81*27=2187=87 (mod 100)
a4=3^87 mod 100
=3^7 mod 100=87.
So after a3, all our ai have last digit 87. So our answer is just 87.
Wednesday, March 27, 2013
Another Short Problem
I was looking at other competitions that I would consider doing in college, and I found out about the International Mathematics Competition for University Students. (http://www.imc-math.org/). I could enter as part of a university team (provided I get chosen for said team), or, failing that, I could go as an individual student. My curiosity piqued, I looked at the problems for the previous year of the competition, available here: http://www.imc-math.org.uk/imc2012/IMC2012-day1-questions.pdf
The first question was pretty trivial, and I got it immediately, I decided to post it here, and then go to bed. (This was a good way to make me feel a bit better about myself after my lack of success with the Putnam questions).
For every positive integer n, let p(n) denote the number of ways to express
n as a sum of positive integers. For instance, p(4) = 5 because
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1.
Also define p(0) = 1.
Prove that p(n) − p(n − 1) is the number of ways to express n as a sum of integers
each of which is strictly greater than 1.
This means that we have to prove that there are p(n-1) ways to express n as a sum of positive integers, with the restriction that you must include a 1 in the sum.
However, this is obviously true, as take such a sum, and subtract the 1. The remaining integers sum to n-1, and can be anything. And there are precisely p(n-1) ways to get a sum of n-1. So we are done.
The rest of the problems from this contest actually seem really cool, so I will do more of them in the future.
The first question was pretty trivial, and I got it immediately, I decided to post it here, and then go to bed. (This was a good way to make me feel a bit better about myself after my lack of success with the Putnam questions).
For every positive integer n, let p(n) denote the number of ways to express
n as a sum of positive integers. For instance, p(4) = 5 because
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1.
Also define p(0) = 1.
Prove that p(n) − p(n − 1) is the number of ways to express n as a sum of integers
each of which is strictly greater than 1.
This means that we have to prove that there are p(n-1) ways to express n as a sum of positive integers, with the restriction that you must include a 1 in the sum.
However, this is obviously true, as take such a sum, and subtract the 1. The remaining integers sum to n-1, and can be anything. And there are precisely p(n-1) ways to get a sum of n-1. So we are done.
The rest of the problems from this contest actually seem really cool, so I will do more of them in the future.
Update (March 27th)
So I am working currently on the other problems from that same Putnam exam, and having little success. Under normal circumstances, I would just forget about them and move on. But we can't be having that. If I actually want to get better at this sort of thing, it is important that I finish what I start. (This is applicable to most pursuits actually). I hope to solved at least one of the remaining 12 problems by this weekend.
I really have very little tenacity, it's a pretty big problem. I tend to give up things when they become difficult. If I wish to pursue a career in math, or actually in anything, I need to be able to persevere. This project provides some external motivation for that perseverance, as I need something to document. I am confident that if I pursue this project seriously, I will get some sort of actual improvement. Which is why, despite the fact that my blog entries will not be entertaining for most people and I will have no "interesting" final product, I want to to continue with it.
I really have very little tenacity, it's a pretty big problem. I tend to give up things when they become difficult. If I wish to pursue a career in math, or actually in anything, I need to be able to persevere. This project provides some external motivation for that perseverance, as I need something to document. I am confident that if I pursue this project seriously, I will get some sort of actual improvement. Which is why, despite the fact that my blog entries will not be entertaining for most people and I will have no "interesting" final product, I want to to continue with it.
Tuesday, March 26, 2013
Problem for 3/25
This is the very first problem of the very first Putnam exam. (All Putnam problems are taken from the book The William Lowell Putnam Mathematical Competition 1985–2000: Problems, Solutions, and Commentary, published by the Mathematical Association of America. )
Problem:
Determine, with proof, the number of ordered triples (A1,A2,A3) of sets which
have the property that
(i) A1 ∪ A2 ∪ A3 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and
(ii) A1 ∩ A2 ∩ A3 = ∅,
where ∅ denotes the empty set. Express the answer in the form 2^a * 3^b * 5^c *7^d, where a, b,
c, and d are nonnegative integers. ∪ means union, ∩ means intersection.
This is a very good problem for me to begin with, because it's pretty simple to state, and requires no complicated ideas to prove. Hopefully anyone reading this blog can understand it.
I solved the problem in like 5-10 minutes, but I forgot what an "ordered triple" was, so I thought I made a mistake, and continued for 1 hour, and had to use the book's hint, and arrived at the same solution as I had the first time, and then realized that an ordered triple means that (a,b,c) and (c,b,a) are different, and banged my head loudly against the desk.
Please please comment about how clear these solutions are, as I am pretty bad at explaining things.
So, I have two solutions to share:
Solution #1: (solution I found with a hint from the book):
This is basically saying, how many ways can you split {1,..10} into 3 sets, where elements can be in two sets at once, but not 3.
We can make a Venn diagram to represent this actually. Draw a Venn Diagram with 3 circles (like this), and cross out the section where all 3 circles intersect. (This is the section in white on the picture) If we fill this diagram, excluding the crossed-out part, with the numbers from 1 to 10, we can take the numbers in our 3 circles as A1, A2, A3. There are 6 different spaces in the Venn Diagram in which we can put numbers. So each number from 1 to 10 can go into any of the 6 spaces, so there are 6^10=2^10 * 3^10 ways of doing this.
Solution #2: (my solution)
Replace {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} with {1,2,3,4,....n}.
And call the number of sets f(n). I'm just going to find out how to compute f(n) in general, and then compute f(10). We do this by recursion. If we have a triple (A1, A2, A3) for some n, and then we replace n with n+1. That same triple satisfies the second property, but not the first. We can fix this by inserting n+1 into at least one of our sets.
(If we take a triple for n+1, we can remove all instances of n+1 and get a triple for n, so we don't "miss" any).
So how many ways can we do this? Well, we can add n+1 into A1, A2, or A3, which is 3 ways. But we can also add n+1 into 2 sets, as there is only a problem if it's in all 3. There are also 3 ways of doing that (adding it to A1, A2, or A2,A3, or A1,A3). So for each triple in n, there are 6 triples in n+1, so f(n+1)=6f(n).
f(1)=6, (Our choices are ({1},∅,∅), ({1},{1},∅) and all reorderings thereof).
So f(n)=6^n, f(10)=6^10=2^10 * 3^10.
I think the first solution is very nice, and that this is a pretty good problem, if a bit easy.
What I can take away from this is that early Putnam problems are not that hard(in general most contests get more difficult from year to year), and that I should really know what an ordered triple is.
Problem:
Determine, with proof, the number of ordered triples (A1,A2,A3) of sets which
have the property that
(i) A1 ∪ A2 ∪ A3 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and
(ii) A1 ∩ A2 ∩ A3 = ∅,
where ∅ denotes the empty set. Express the answer in the form 2^a * 3^b * 5^c *7^d, where a, b,
c, and d are nonnegative integers. ∪ means union, ∩ means intersection.
This is a very good problem for me to begin with, because it's pretty simple to state, and requires no complicated ideas to prove. Hopefully anyone reading this blog can understand it.
I solved the problem in like 5-10 minutes, but I forgot what an "ordered triple" was, so I thought I made a mistake, and continued for 1 hour, and had to use the book's hint, and arrived at the same solution as I had the first time, and then realized that an ordered triple means that (a,b,c) and (c,b,a) are different, and banged my head loudly against the desk.
Please please comment about how clear these solutions are, as I am pretty bad at explaining things.
So, I have two solutions to share:
Solution #1: (solution I found with a hint from the book):
This is basically saying, how many ways can you split {1,..10} into 3 sets, where elements can be in two sets at once, but not 3.
We can make a Venn diagram to represent this actually. Draw a Venn Diagram with 3 circles (like this), and cross out the section where all 3 circles intersect. (This is the section in white on the picture) If we fill this diagram, excluding the crossed-out part, with the numbers from 1 to 10, we can take the numbers in our 3 circles as A1, A2, A3. There are 6 different spaces in the Venn Diagram in which we can put numbers. So each number from 1 to 10 can go into any of the 6 spaces, so there are 6^10=2^10 * 3^10 ways of doing this.
Solution #2: (my solution)
Replace {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} with {1,2,3,4,....n}.
And call the number of sets f(n). I'm just going to find out how to compute f(n) in general, and then compute f(10). We do this by recursion. If we have a triple (A1, A2, A3) for some n, and then we replace n with n+1. That same triple satisfies the second property, but not the first. We can fix this by inserting n+1 into at least one of our sets.
(If we take a triple for n+1, we can remove all instances of n+1 and get a triple for n, so we don't "miss" any).
So how many ways can we do this? Well, we can add n+1 into A1, A2, or A3, which is 3 ways. But we can also add n+1 into 2 sets, as there is only a problem if it's in all 3. There are also 3 ways of doing that (adding it to A1, A2, or A2,A3, or A1,A3). So for each triple in n, there are 6 triples in n+1, so f(n+1)=6f(n).
f(1)=6, (Our choices are ({1},∅,∅), ({1},{1},∅) and all reorderings thereof).
So f(n)=6^n, f(10)=6^10=2^10 * 3^10.
I think the first solution is very nice, and that this is a pretty good problem, if a bit easy.
What I can take away from this is that early Putnam problems are not that hard(in general most contests get more difficult from year to year), and that I should really know what an ordered triple is.
Background
I guess I should explain who I am and define clearly what I am trying to do, as competitive math is not really something most people know much about.
My name is Irit, I, for some perverse reason, enjoy doing math. I'm currently taking Math 2240 at Cornell University, and auditing Math 4130 and Math 4540.
The purpose of this project is to prepare for undergraduate math competitions, primarily Putnam.
There are two main reasons I want to do this, actually 3.
1. Success in undergraduate competitions is helpful for applying for summer research programs, certain jobs, and graduate schools.
2. I have done pretty badly in high school math competitions (primarily the AMC and AIME), and I would like to redeem myself in college.
3. I think such competitions can be a lot of fun.
The basic routine will be something like:
1 hour every day of solving problems, doing some research, and/or blogging.
Occasionally, I will take 3-6 hours to do some full competition.
I'm going to talk more about competitions and what they are later, as I don't want to give too much information in one sitting.
My name is Irit, I, for some perverse reason, enjoy doing math. I'm currently taking Math 2240 at Cornell University, and auditing Math 4130 and Math 4540.
The purpose of this project is to prepare for undergraduate math competitions, primarily Putnam.
There are two main reasons I want to do this, actually 3.
1. Success in undergraduate competitions is helpful for applying for summer research programs, certain jobs, and graduate schools.
2. I have done pretty badly in high school math competitions (primarily the AMC and AIME), and I would like to redeem myself in college.
3. I think such competitions can be a lot of fun.
The basic routine will be something like:
1 hour every day of solving problems, doing some research, and/or blogging.
Occasionally, I will take 3-6 hours to do some full competition.
I'm going to talk more about competitions and what they are later, as I don't want to give too much information in one sitting.
Monday, March 25, 2013
Project Change
I realized, after much deliberation, that I honestly was not enjoying my project. Cooking is fun, but I felt I was limited in what I could cook, and documenting it was a pain, and I felt it was sort of meaningless. The project was really becoming a chore. The straw that hit the camel's back was when I was given an assignment to read a past journal. The student, Niko Schaff, clearly loved his project, and, as a result, his journals were entertaining to read. Mine felt flat in comparison.
So I felt it was important to change my project to one that I could talk more easily about. I have always enjoyed math (more about my mathematical background will be revealed later)
I will attend a university next year (no idea which). There is a collegiate math competition called Putnam. I would probably end up entering this competition. To that end, I wish to improve my skills in problem-solving and competitive math.
(It is actually quite fortuitous that I could not pick a name for my blog, as a cooking-related name would be out of place).
I have begun preparations today, and I will document what I've done tomorrow, when I give my math background. (I think it will make much more sense in that context.)
So I felt it was important to change my project to one that I could talk more easily about. I have always enjoyed math (more about my mathematical background will be revealed later)
I will attend a university next year (no idea which). There is a collegiate math competition called Putnam. I would probably end up entering this competition. To that end, I wish to improve my skills in problem-solving and competitive math.
(It is actually quite fortuitous that I could not pick a name for my blog, as a cooking-related name would be out of place).
I have begun preparations today, and I will document what I've done tomorrow, when I give my math background. (I think it will make much more sense in that context.)
3 things I wish I had done differently.
1. I wish I had been more whole-hearted with my journal entries, and with my project in general. It feels as if it is becoming a chore.
2. I wish I had done more last week, due to travel and other circumstances, I couldn't really accomplish anything.
3. I honestly wish I had picked a different topic, I am not really interested in journaling about cooking. I am planning on changing my project, and will probably decide whether I do that tonight.
2. I wish I had done more last week, due to travel and other circumstances, I couldn't really accomplish anything.
3. I honestly wish I had picked a different topic, I am not really interested in journaling about cooking. I am planning on changing my project, and will probably decide whether I do that tonight.
Monday, March 18, 2013
Aminia Chicken Curry
Last week, I made a chicken curry based on a recipe from the internet. Aminia is a restaurant in Kolkata, my mother's hometown. It's a Muslim restaurant, and the only place her father would take her out to eat, so this dish both has some personal significance, and is relevant to my Muslim heritage. The video I used made a mutton curry, I replaced the mutton with chicken.
This process is actually pretty laborious. You need to boil many eggs and potatoes beforehand, and chop many vegetables, before doing the actual work of making the curry. My difficulties were compounded by the fact the video was in Bengali, which I can't understand very well, and my mother was out, so I couldn't ask her to translate. So I had to figure out what and how much ingredients I needed to use.
Because the recipe was so inexact, and I did not even follow it exactly, I will not include a recipe at this time. The video I used is available, if you can speak Bengali or just want to get a general idea of what goes into this curry.
http://www.youtube.com/watch?v=te1EYPFrFpA
The result was satisfactory, I enjoyed eating it. However, I was really stressed when making it, and the proportions were pretty terrible (I only realized part of the way through that the person in the video was making much more curry than I was), so there is obviously some room for improvement.
Pictures:
This process is actually pretty laborious. You need to boil many eggs and potatoes beforehand, and chop many vegetables, before doing the actual work of making the curry. My difficulties were compounded by the fact the video was in Bengali, which I can't understand very well, and my mother was out, so I couldn't ask her to translate. So I had to figure out what and how much ingredients I needed to use.
Because the recipe was so inexact, and I did not even follow it exactly, I will not include a recipe at this time. The video I used is available, if you can speak Bengali or just want to get a general idea of what goes into this curry.
http://www.youtube.com/watch?v=te1EYPFrFpA
The result was satisfactory, I enjoyed eating it. However, I was really stressed when making it, and the proportions were pretty terrible (I only realized part of the way through that the person in the video was making much more curry than I was), so there is obviously some room for improvement.
Pictures:
 |
| Mixed spices and liquid ingredients |
 |
| Essentially finished curry |
 |
| Vegetables, to be added near the end |
In Class Entry: 3/18
I was tasked with reading a journal of a previous WISE student last weekend. The student in question, Niko Schaff, was investing in the stock market for his project.
What I got out of doing this was that it is very important that journal entries be interesting and entertaining, as, in theory, they are actually being read. Niko's entries were relatively long, varied in topic, he talked sometimes about the philosophy and ethics of investing, sometimes about future plans, sometimes about what he did today. They were all a joy to read. His research entries were also very instructive, he explained things very simply, so anyone could understand.
Unfortunately, he made some grammar mistakes (e.g. a few theirs, theres, and they'res confused), sometimes his writing style was sort of strange. I think he was becoming a little more stressed and pressed for time closer to the end, so for a while his entries got much shorter.
I think my journal entries have been kind of boring, and I want to change that. So I will try to perhaps write them more like Niko does. I also want to do more research to inform my readers, as most people here know very little about India or Indian food. To that end, I will also take a leaf out of Niko's book and provide more extensive research entries.
What I got out of doing this was that it is very important that journal entries be interesting and entertaining, as, in theory, they are actually being read. Niko's entries were relatively long, varied in topic, he talked sometimes about the philosophy and ethics of investing, sometimes about future plans, sometimes about what he did today. They were all a joy to read. His research entries were also very instructive, he explained things very simply, so anyone could understand.
Unfortunately, he made some grammar mistakes (e.g. a few theirs, theres, and they'res confused), sometimes his writing style was sort of strange. I think he was becoming a little more stressed and pressed for time closer to the end, so for a while his entries got much shorter.
I think my journal entries have been kind of boring, and I want to change that. So I will try to perhaps write them more like Niko does. I also want to do more research to inform my readers, as most people here know very little about India or Indian food. To that end, I will also take a leaf out of Niko's book and provide more extensive research entries.
Saturday, March 16, 2013
Why make ____?
The question has been posed to me, "why do I make the particular dishes I make?" The answer is primarily because many of them were quick and easy, thus suitable for making in college, and because they use ingredients we already have. There isn't a super-cohesive set of principles, nor do I think should there be.
However, I have ended up making many rice dishes, and I think it might be worthwhile to spend some time focusing on how rice is handled in different countries, and their similarities. (The Spanish, Balkans, and Iranians all have dishes that are basically pulao, they are known as paella, pilav, and polo, respectively.)
The first "complicated" thing I made was a chicken curry, modeled after one from a Muslim restaurant my mother used to frequent as a child. I chose this primarily because of its relevance to my cultural heritage, and will document it tomorrow.
However, I have ended up making many rice dishes, and I think it might be worthwhile to spend some time focusing on how rice is handled in different countries, and their similarities. (The Spanish, Balkans, and Iranians all have dishes that are basically pulao, they are known as paella, pilav, and polo, respectively.)
The first "complicated" thing I made was a chicken curry, modeled after one from a Muslim restaurant my mother used to frequent as a child. I chose this primarily because of its relevance to my cultural heritage, and will document it tomorrow.
An Indian Pantry
It is obviously important, when cooking, to keep a well stocked pantry. I sought to learn what sort of ingredients, spices, etc. I would need, if I wanted to be able to cook most Indian dishes. This list is primarily from prior knowledge, with additional information provided by research. Most of these items are used all over India.
Misc:
Rice, preferably Basmati.
Oil for cooking.
Ghee (clarified butter, used a substitute for oil in some cases)
Spices:
Ginger paste/garlic paste
Turmeric
Asafoetida (commonly called heeng (I have no idea how to properly Romanize this))
Nigella seeds (called Kalonji)
Paprika
Chili Powder
Coriander seeds and powder
Cumin
Cloves
Cinnamon
Bay leaves
Curry leaves
Peppercorns
Rock Salt
Mustard seeds
Vegetables:
Onions (used in absolutely everything)
Tomatoes (used to provide liquid)
Fenugreek (labeled Methi in Indian stores)
Legumes:
Chickpeas, lentils.
Meats are somewhat interchangeable, with the exception of pork, which is very rare in India. You can basically just buy some arbitrary cut of meat and make something with it, so there isn't a need to "stock up" on particular meat. Seafood is similar, but you need to have a pretty good idea of what fish to use. (Generally relatively bland fish such as tilapia work, avoid fish that have no place in Indian cuisine that are strongly flavored, such as salmon). Shrimp is also very common. Also, meat and fish does not keep indefinitely, so putting it in a "pantry" is often impractical, but I think these are worth mentioning here nonetheless.
Misc:
Rice, preferably Basmati.
Oil for cooking.
Ghee (clarified butter, used a substitute for oil in some cases)
Spices:
Ginger paste/garlic paste
Turmeric
Asafoetida (commonly called heeng (I have no idea how to properly Romanize this))
Nigella seeds (called Kalonji)
Paprika
Chili Powder
Coriander seeds and powder
Cumin
Cloves
Cinnamon
Bay leaves
Curry leaves
Peppercorns
Rock Salt
Mustard seeds
Vegetables:
Onions (used in absolutely everything)
Tomatoes (used to provide liquid)
Fenugreek (labeled Methi in Indian stores)
Legumes:
Chickpeas, lentils.
Meats are somewhat interchangeable, with the exception of pork, which is very rare in India. You can basically just buy some arbitrary cut of meat and make something with it, so there isn't a need to "stock up" on particular meat. Seafood is similar, but you need to have a pretty good idea of what fish to use. (Generally relatively bland fish such as tilapia work, avoid fish that have no place in Indian cuisine that are strongly flavored, such as salmon). Shrimp is also very common. Also, meat and fish does not keep indefinitely, so putting it in a "pantry" is often impractical, but I think these are worth mentioning here nonetheless.
Restaurant Indian Cuisine.
The question was posed to me why so many "restaurant" Indian dishes come from the North. (e.g. tandoori chicken, naan, etc). I couldn't furnish an answer so I decided to do some research. However, this was actually pretty fruitless. I learned that there were many Sikh laborers in the U.S in the early 20th century. Sikhs are from Punjab, an area in North India, so I guessed that this was the reason why there were so many North Indian restaurants. However, this doesn't really explain why this is true in other countries. As it turns out, my theory was correct but for the wrong reasons. My mother explained to me that there is not a great tradition of restaurants in India, and most Indian restaurants are owned by Punjabis. So Punjabis who emigrated from India took their traditions with them, and established new restaurants. Afterwards, I wanted to find an internet source that said something similar, but again, I was fruitless. (Searching for this sort of demographic information is apparently quite difficult).
This is not to say that all Indian restaurants are owned by Punjabis, or even that all dishes in an Indian restaurant owned by Punjabis are North Indian. Partially because exact authenticity is not a concern when not marketing to Indians, many such restaurants feature dishes from all over India, such as idli or dosa. (This is not a criticism, it's not as if they don't have a right to do this, and it is definitely a sound business decision)
This is not to say that all Indian restaurants are owned by Punjabis, or even that all dishes in an Indian restaurant owned by Punjabis are North Indian. Partially because exact authenticity is not a concern when not marketing to Indians, many such restaurants feature dishes from all over India, such as idli or dosa. (This is not a criticism, it's not as if they don't have a right to do this, and it is definitely a sound business decision)
Sunday, March 10, 2013
Response to Barn Video
In WISE on Wednesday, we watched a video made by a past WISE student, as his project, documenting the project of someone else, who was trying to build a barn. I think the video was well-made, as it captured well the process of doing such a project. He documented both the successes of the project (cutting of the beams, finishing the barn, figuring out how to transport cut beams), and the failures (delay of barn, arguments with father, etc.), and dealt with common pitfalls in such projects (things taking longer than expected). I think the video certainly serves its purpose: to communicate the experience of doing a WISE project. It is also quite fitting, given the purpose of the video and the subject matter, that most of the music was made by students.
The biggest criticism I can think of is that the title screen that plays clips from the video often features a very annoying sawing sound, and that is honestly quite minor.
The biggest criticism I can think of is that the title screen that plays clips from the video often features a very annoying sawing sound, and that is honestly quite minor.
Tomato Rice
This is another pulao dish in the vein of junglee pulao. However, it is primarily South Indian. It is also very simple:
The recipe is essentially identical to this:
http://www.umakitchen.com/2012/08/tomato-rice.html
I used no chili, no mustard seeds, and used 1.5 cups of rice instead of 1 cup.
The result was excellent. I was completely happy with how it turned out. I will probably revisit this again, to make sure I can make it with no recipe, as it is something I want to make often in the future.
The recipe is essentially identical to this:
http://www.umakitchen.com/2012/08/tomato-rice.html
I used no chili, no mustard seeds, and used 1.5 cups of rice instead of 1 cup.
The result was excellent. I was completely happy with how it turned out. I will probably revisit this again, to make sure I can make it with no recipe, as it is something I want to make often in the future.
Aloo Methi
I am basically going to write all the posts for this week over this weekend, because I am obviously very good at time management. On Sunday I made aloo methi (literally fenugreek potato). In essence, it is potato, cooked in mustard oil with fenugreek leaves. It is incredibly easy to make, but is also an acquired taste.
Recipe:
Small potatoes.
Mustard oil.
Water.
Chili
Fenugreek leaves.
Nigella seeds
Recipe:
Cook the seeds in the mustard oil until they begin to splutter, add a chili pepper.
When the spices are cooked, add the potatoes, mix until coated fully with oil.
Add crushed fenugreek and cover potatoes with water. (If you are using fresh greens, no water is necessary)
Cover pot and cook until potatoes are soft.
If there is remaining water, uncover the pot and cook until water is evaporated.
Result:
This honestly tasted terrible. I didn't do anything wrong in preparing it, I just don't particularly like mustard oil or fenugreek. I should perhaps avoid those two ingredients in the future.
Recipe:
Small potatoes.
Mustard oil.
Water.
Chili
Fenugreek leaves.
Nigella seeds
Recipe:
When the spices are cooked, add the potatoes, mix until coated fully with oil.
Add crushed fenugreek and cover potatoes with water. (If you are using fresh greens, no water is necessary)
Cover pot and cook until potatoes are soft.
If there is remaining water, uncover the pot and cook until water is evaporated.
Result:
This honestly tasted terrible. I didn't do anything wrong in preparing it, I just don't particularly like mustard oil or fenugreek. I should perhaps avoid those two ingredients in the future.
 |
| Cooking the nigella |
 |
| Finished product |
Sunday, March 3, 2013
Indian Cuisine by Region
India is a pretty diverse place. Between states, there are massive differences in customs, language, culture, and cuisine. The level of diversity is not present in any other country, most people don't realize that there is no real "national language" of India. (There are around 21 official languages, probably the two most widely spoken are Hindi and English) So I think a blog related to Indian food would not be complete without at least a cursory explanation of the differences in Indian cuisine by region. There are 28 states, and several territories in India, one post is not really enough to deal with the specific cuisines of all of them. So I am just going to talk about North, South, and East, and West.
South: This is the region my father comes from. It contains states such as Kerala and Tamil Nadu. It is predominantly Hindu, and has many Brahmins, so vegetarian dishes are prevalent. Southerners also often cook with tamarind and coconut milk as flavoring agents. They also use sea-fish in coastal areas. Regional dishes include avial, a mixture of vegetables cooked in coconut milk, dosa, a crepe made with rice and lentil flour, and idli, a cake (not sweet) made with rice and lentil batter.
East: Includes Kolkata, the city where my mother is from. It contains states such as West Bengal and Bihar. There are many "Bengalis" in this region, who eat primarily of river fish, notably the hilsa (similar to shad),and use sugar in their savory dishes. They also use mustard seeds and mustard oil. There are also more Muslims in the East, who often eat meat, particularly mutton, potatoes, and other root vegetables, among other things.
North: This is where a lot of "restaurant" Indian food originates. It contains states such as Punjab. Here the tandoor, a clay oven, is very prominent. Thus popular dishes in the North include Naan and Tandoori Chicken.
West: Western cuisine has been described as a combination of Northern and Southern. Probably the most well-known Western specialty is Vindaloo, a curry made with vinegar. West India contains states such as Goa and Maharashtra. Goan cuisine is actually pretty special in itself, as Goa was a Portugese colony for quite some time, and Goan food reflects this. (They use more pork and beef than the rest of India, and are noted for their sausages, which are similar to the Iberian chorizo)
South: This is the region my father comes from. It contains states such as Kerala and Tamil Nadu. It is predominantly Hindu, and has many Brahmins, so vegetarian dishes are prevalent. Southerners also often cook with tamarind and coconut milk as flavoring agents. They also use sea-fish in coastal areas. Regional dishes include avial, a mixture of vegetables cooked in coconut milk, dosa, a crepe made with rice and lentil flour, and idli, a cake (not sweet) made with rice and lentil batter.
East: Includes Kolkata, the city where my mother is from. It contains states such as West Bengal and Bihar. There are many "Bengalis" in this region, who eat primarily of river fish, notably the hilsa (similar to shad),and use sugar in their savory dishes. They also use mustard seeds and mustard oil. There are also more Muslims in the East, who often eat meat, particularly mutton, potatoes, and other root vegetables, among other things.
North: This is where a lot of "restaurant" Indian food originates. It contains states such as Punjab. Here the tandoor, a clay oven, is very prominent. Thus popular dishes in the North include Naan and Tandoori Chicken.
West: Western cuisine has been described as a combination of Northern and Southern. Probably the most well-known Western specialty is Vindaloo, a curry made with vinegar. West India contains states such as Goa and Maharashtra. Goan cuisine is actually pretty special in itself, as Goa was a Portugese colony for quite some time, and Goan food reflects this. (They use more pork and beef than the rest of India, and are noted for their sausages, which are similar to the Iberian chorizo)
Qeema
On Friday, I made Qeema, or ground meat. This is a very standard Muslim dish. I used the National Indian Association for Women's cookbook for guidelines, but made some small changes, as their recipe was very terse. The steps that go into this recipe are actually pretty standard to many Indian dishes. So it would be very instructive for me to provide a step-by-step account of what I did.
You will need:
4 Medium Onions**
1 lb. ground meat.
Oil
3 tsp Coriander**
3.5 tsp Cumin**
1.5 tsp Chili Powder**
Salt
1.5 tsp ginger paste **
1.5 tsp garlic paste**
Optional:
Whatever "hard' vegetables you want:
(e.g. potato, carrot, turnip)
Peas (frozen)
Some tomato.
**these are all things that you absolutely need to have if you want to cook almost anything Indian.
First, chop the onions and cook them in oil, in a large pot, until they completely caramelize. (The degree to which you cook the onions depends on where your dish is from, this is a Muslim dish, so cook the onions completely.)
Add the ginger and garlic paste, then the meat, and salt. Cover the pot and cook for about 15 minutes, until the meat is brown. Add the spices and "hard" vegetables, and the tomato if you elected to include that. Cook for another 6-7 minutes. Add water and then cook on a low heat setting. Add the frozen peas just a little bit before you stop cooking, you want enough time to thaw the peas and cook them a bit.
If this were any sort of curry, the steps would actually be quite similar, but you would add a large amount of water and/or tomato at some point to provide a liquid. (This is why this recipe is so instructive).
The result came out pretty well, the biggest issue was that I got impatient and did not caramelize the onions enough, but that was fairly minor.
You will need:
4 Medium Onions**
1 lb. ground meat.
Oil
3 tsp Coriander**
3.5 tsp Cumin**
1.5 tsp Chili Powder**
Salt
1.5 tsp ginger paste **
1.5 tsp garlic paste**
Optional:
Whatever "hard' vegetables you want:
(e.g. potato, carrot, turnip)
Peas (frozen)
Some tomato.
**these are all things that you absolutely need to have if you want to cook almost anything Indian.
First, chop the onions and cook them in oil, in a large pot, until they completely caramelize. (The degree to which you cook the onions depends on where your dish is from, this is a Muslim dish, so cook the onions completely.)
Add the ginger and garlic paste, then the meat, and salt. Cover the pot and cook for about 15 minutes, until the meat is brown. Add the spices and "hard" vegetables, and the tomato if you elected to include that. Cook for another 6-7 minutes. Add water and then cook on a low heat setting. Add the frozen peas just a little bit before you stop cooking, you want enough time to thaw the peas and cook them a bit.
If this were any sort of curry, the steps would actually be quite similar, but you would add a large amount of water and/or tomato at some point to provide a liquid. (This is why this recipe is so instructive).
The result came out pretty well, the biggest issue was that I got impatient and did not caramelize the onions enough, but that was fairly minor.
 |
| Cooking the onions |
 |
| Adding spices and vegetables |
 |
| Finally complete! |
Rice
A few days ago, I made rice. This may seem stupid to blog about, but it is something absolutely fundamental in Indian cooking. Furthermore, I made it in a perhaps unconventional manner: in a microwave. I think my readership (or lack thereof) will find knowing how too do this useful at some point. So here is the method:
You need a little less than one cup of rice per person. Wash the rice in a strainer until the water draining out runs clear. Now, place the rice in a microwave-safe vessel, with a lid. Now, add water. You want probably 1.5 cups water for each cup of rice. (I use Basmati rice, because, despite being white rice, it has a lower glycemic index, and my father is a diabetic. Basmati rice tends to expand more, so I needed 2 cups of water per cup of rice). Cook the rice for 6 minutes covered, 8 minutes uncovered, then 6 minutes covered again.
Alternatively, you could just buy a rice cooker. That is probably a better idea.
You need a little less than one cup of rice per person. Wash the rice in a strainer until the water draining out runs clear. Now, place the rice in a microwave-safe vessel, with a lid. Now, add water. You want probably 1.5 cups water for each cup of rice. (I use Basmati rice, because, despite being white rice, it has a lower glycemic index, and my father is a diabetic. Basmati rice tends to expand more, so I needed 2 cups of water per cup of rice). Cook the rice for 6 minutes covered, 8 minutes uncovered, then 6 minutes covered again.
Alternatively, you could just buy a rice cooker. That is probably a better idea.
Wednesday, February 27, 2013
Reflection: What has changed?
So I have cooked a fair amount of things. I guess I feel now more "comfortable" in the kitchen than I have ever done before. I am no longer afraid of cooking, and I feel that if I were forced to improvise a meal, it would turn out acceptably. I think I should (finally) focus on more Indian things, and should also improvise and experiment more.
I guess to all of you who already cook this is not impressive. But I am always really anxious every time I cook, and am afraid of doing something "wrong". I am now a bit more confident, and a bit more ready to trust my instincts. I have no regrets pursuing this project. (I think at least)
I guess to all of you who already cook this is not impressive. But I am always really anxious every time I cook, and am afraid of doing something "wrong". I am now a bit more confident, and a bit more ready to trust my instincts. I have no regrets pursuing this project. (I think at least)
Pasta!!!
This is probably the last of the non-Indian basic stuff that I make, for reasons I will outline afterwards. But, as evident from the title, I am blogging today about pasta. I made a pasta dish, which is insignificant in itself, but pasta dishes are very important to me. When I was younger, pasta was one of the few things I would eat, and one of the few things I genuinely enjoyed. To this day, I enjoy both making and eating pasta.
Without further ado: the recipe
The dish is basically pasta with a sauce made from milk, sausage, kale, and lemon juice.
I used sausage from the Piggery, expensive, but absolutely worth it.
All of the individual elements in the dish were prominent, resulting in a pleasant flavor. The proportions were also to my liking, the same weight of pasta, sausage, and kale. I never felt there was too much or too little of one ingredient. (It is often the meat in such dishes that is scarce).
Here is a picture of how the dish turned out:
As an aside, the best way to remove sausages from their casing is to score the casing with a knife, and use the knife to rip a line down the sausage, and then remove the casing as you would a jacket from a person.
Without further ado: the recipe
The dish is basically pasta with a sauce made from milk, sausage, kale, and lemon juice.
I used sausage from the Piggery, expensive, but absolutely worth it.
All of the individual elements in the dish were prominent, resulting in a pleasant flavor. The proportions were also to my liking, the same weight of pasta, sausage, and kale. I never felt there was too much or too little of one ingredient. (It is often the meat in such dishes that is scarce).
Here is a picture of how the dish turned out:
As an aside, the best way to remove sausages from their casing is to score the casing with a knife, and use the knife to rip a line down the sausage, and then remove the casing as you would a jacket from a person.
Tuesday, February 26, 2013
HW Assignment: Responses to Other Blogs:
I read Dennis Jung's blog about Fitness and positive habit-building. I am impressed with his progress, but noticed something of a pattern in where he did not meet his schedule. He consistently wakes up later than he plans to. While this may seem like a problem, I argue that it is not. People naturally have different sleep patterns, and ideal times for them to wake up. I think if Dennis imposes on himself too much, he may force himself into a sleep schedule that does not suit him, and that would be more detrimental than beneficial. He has already become much more productive, so it think he should consider planning the rest of his day around the time he would actually prefer to wake up.
I also read Balazs Szegletes' blog about Hungarian Cooking While the dishes look excellent, I would really appreciate some more background about them. Hungarian cooking is a subject unfamiliar both to me, and to most of his readership. I therefore think it is important that he provide historical or cultural context to what he makes, in order to better educate his readers. (I tried to do this to some extent in my post on junglee pulao).
I also read Balazs Szegletes' blog about Hungarian Cooking While the dishes look excellent, I would really appreciate some more background about them. Hungarian cooking is a subject unfamiliar both to me, and to most of his readership. I therefore think it is important that he provide historical or cultural context to what he makes, in order to better educate his readers. (I tried to do this to some extent in my post on junglee pulao).
Junglee Pulao
A few days ago, I made junglee pulao, the first actual Indian dish in this little adventure. Obviously, many more are coming. Junglee pulao means something like "crazy rice" in Hindi, because that is precisely what it is. The dish is a hodgepodge of things, it is supposed to use spices and ingredients that one would already have around the house, such as tomatoes and potatoes. Many choose to incorporate leftover vegetable and meat dishes into it. Keeping this in mind, making it using a recipe would be somewhat silly. (Also my mother knew the general steps by heart)
Cooking the dish did not take very long (total preparation and cooking time took maybe an hour at most), and since it does not require that many specific ingredients, junglee pulao is an ideal thing for me to make in college. (Also I can impress Americans by cooking something "ethnic").
The result was actually quite delicious, and looked like this:
For the curious, a sample recipe is here:
http://indianfood.about.com/od/ricerecipes/r/jungleepulao.html
It's somewhat similar to the method I used, but I used no meat.
Cooking the dish did not take very long (total preparation and cooking time took maybe an hour at most), and since it does not require that many specific ingredients, junglee pulao is an ideal thing for me to make in college. (Also I can impress Americans by cooking something "ethnic").
The result was actually quite delicious, and looked like this:
For the curious, a sample recipe is here:
http://indianfood.about.com/od/ricerecipes/r/jungleepulao.html
It's somewhat similar to the method I used, but I used no meat.
Subscribe to:
Posts (Atom)