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.
Saturday, March 30, 2013
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.
Subscribe to:
Posts (Atom)