Use this place to post your ideas, solutions, comments, generalisations for Problems from the 2009 Putnam exam. The first one (A1) is not difficult. (As said before, the first problem is often the easiest problem.)
So... I'm pretty sure I have the solution to B1, but I feel like I'm kinda cheating since I did this solution last year during the exam. I could be wrong, but i think this is where I got my points. Well, here is something like what I wrote:
First, since every rational number can be expressed as a ratio of integers, we need only to show that any integer can be written as the quotient of products of prime factorials. In order to write an integer, say k, in this form we first need its prime factors, p1 p2 p3... pN. We then multiply their factorials together to get p1!*p2!*p3!*...*pN!. Clearly, this is greater than k. We need to divide by (p1-1)!*(p2-1)!*...*(pN-1)!. These are not necessarily primes however. We can divide by their prime factorials however. We continue in this manner for p1-2, p1-3 and so on until we are dividing or multiplying by only prime factorials. applying this to the example let us first look at 10. It's prime factors are 5 and 2. we then start with 5!*2!, divide first by the factorials of the prime factors of 4, 5-1, which are 2! and 2!. We then have 5!*2!/2!*2!. Since 5-2=3 we divide by 3! which is prime, to give us (5!*2!)/(3!*2!*2!) which simplifies to 5!/(3!*2!). 9 is done in similar fashion to be expressed as (3!*3!)/(2!*2!). Then 10/9 is [5!/(3!*2!)]/[(3!*3!)/(2!*2!)] which reduces to (5!*2!)/(3!*3!*3!).
Greg: First of all, I want to thank for posting a comment and also for being the first person to get the ball rolling. Hopefully this will inspire the rest of us to contribute to the blog.
Yes, your solution is correct. You get 10 out of 10 on this one. I have a slightly different solution.
Consider the set of all numbers which are a quotient of a product of prime factorials. This set of closed under multiplication and division. Since every rational number is a obtained from primes numbers using multiplication and division. It is enough to establish the claim for prime numbers. To this end, we use induction. The base cases: 2 = 2! and 3 = 3!/2! are clear. So assume that all primes < p are of the desired form. Now we have to show that p can also be expressed in this form. Well p = p!/(p-1)! but all prim factors of (p-1)! are less than p [that's the key step]. So by induction hypotheses all those primes have the desired form. Since these numbers which can be expressed a quotient of a product of prime factorial is closed under multiplication and division, we are done.
I think A1 has a nice and straightforward generalisation to 3 dimensions. The idea in 2-dimensions is to chop a square into four equal squares and apply the condition on the function to all 5 squares (4 small and 1 big). In three dimensions, one should be able to do a similar thing. Divide a cube into 8 equal cubes and apply the condition to all the 9 cubes (8 small and 1 big). I did not work out the details in 3-dimensions but this is an idea worth exploring.
I just came across this cute little amusing problem on the Fibonacci numbers: Show that every 3rd Fibonnaci number is even. Give it a try, it is not hard. (Recall that the Fibonnaci sequence is given by 1, 1, 2, 3, 5, 8, 13, ... In general the nth term is obtained by adding the previous two terms.)
I started out with a Mathematical curiosity: What is the smallest area enclosed by a closed curve in which a needle of unit length can be rotated 180? The answer is not a circle or a semi-circle, it is shockingly unbelievable. There is no smallest area for this problem. In other words, no matter how small area (t) you give me, I can construct a curve which encloses an area less than t in which it is possible to rotate the needle 180 degrees. This is the famous Kakeya needle problem. Read more here: http://en.wikipedia.org/wiki/Kakeya_set
Then I talked about the prisoners-hats puzzle. You can read more about it here: http://bekaarbokbok.blogspot.com/2010/07/of-prisoners-and-hats.html
Then Anna presented a very elegant solution of the Fibonnaci problem which I posed in the previous comment (see above) using Mathematical induction.
We then started out talking about the 2009 problem set. We only got to the first problem. But that is fine. Our goal is not to finish all the problems. We do as many as our time and energy permits.
I handed out the problem set for 2008 Putnam. We shall focus on this next week.
I also handed out the course announcement for Math 268: Introduction to Undergraduate research in Mathematics which I will be teaching next semester.
I also talked about my blog (under construction) with the title Ars Longa Vita Brevis. Read about it more here: http://en.wikipedia.org/wiki/Ars_longa,_vita_brevis
Brian, Amy and I also tried to solve A4 from 2009 but we could not get too far with that. We enjoyed thinking however.
So... I'm pretty sure I have the solution to B1, but I feel like I'm kinda cheating since I did this solution last year during the exam. I could be wrong, but i think this is where I got my points. Well, here is something like what I wrote:
ReplyDeleteFirst, since every rational number can be expressed as a ratio of integers, we need only to show that any integer can be written as the quotient of products of prime factorials. In order to write an integer, say k, in this form we first need its prime factors, p1 p2 p3... pN. We then multiply their factorials together to get p1!*p2!*p3!*...*pN!. Clearly, this is greater than k. We need to divide by (p1-1)!*(p2-1)!*...*(pN-1)!. These are not necessarily primes however. We can divide by their prime factorials however. We continue in this manner for p1-2, p1-3 and so on until we are dividing or multiplying by only prime factorials. applying this to the example let us first look at 10. It's prime factors are 5 and 2. we then start with 5!*2!, divide first by the factorials of the prime factors of 4, 5-1, which are 2! and 2!. We then have 5!*2!/2!*2!. Since 5-2=3 we divide by 3! which is prime, to give us (5!*2!)/(3!*2!*2!) which simplifies to 5!/(3!*2!). 9 is done in similar fashion to be expressed as (3!*3!)/(2!*2!). Then 10/9 is [5!/(3!*2!)]/[(3!*3!)/(2!*2!)] which reduces to (5!*2!)/(3!*3!*3!).
Greg: First of all, I want to thank for posting a comment and also for being the first person to get the ball rolling. Hopefully this will inspire the rest of us to contribute to the blog.
ReplyDeleteYes, your solution is correct. You get 10 out of 10 on this one. I have a slightly different solution.
Consider the set of all numbers which are a quotient of a product of prime factorials. This set of closed under multiplication and division. Since every rational number is a obtained from primes numbers using multiplication and division. It is enough to establish the claim for prime numbers. To this end, we use induction. The base cases: 2 = 2! and 3 = 3!/2! are clear. So assume that all primes < p are of the desired form. Now we have to show that p can also be expressed in this form. Well p = p!/(p-1)! but all prim factors of (p-1)! are less than p [that's the key step]. So by induction hypotheses all those primes have the desired form. Since these numbers which can be expressed a quotient of a product of prime factorial is closed under multiplication and division, we are done.
I think A1 has a nice and straightforward generalisation to 3 dimensions. The idea in 2-dimensions is to chop a square into four equal squares and apply the condition on the function to all 5 squares (4 small and 1 big). In three dimensions, one should be able to do a similar thing. Divide a cube into 8 equal cubes and apply the condition to all the 9 cubes (8 small and 1 big). I did not work out the details in 3-dimensions but this is an idea worth exploring.
ReplyDeleteI just came across this cute little amusing problem on the Fibonacci numbers: Show that every 3rd Fibonnaci number is even. Give it a try, it is not hard. (Recall that the Fibonnaci sequence is given by 1, 1, 2, 3, 5, 8, 13, ... In general the nth term is obtained by adding the
ReplyDeleteprevious two terms.)
What happened today:
ReplyDeleteI started out with a Mathematical curiosity: What is the smallest area enclosed by a closed curve in which a needle of unit length can be rotated 180?
The answer is not a circle or a semi-circle, it is shockingly unbelievable. There is no smallest area for this problem. In other words, no matter how small area (t) you give me, I can construct a curve which encloses an area less than t in which it is possible to rotate the needle 180 degrees. This is the famous Kakeya needle problem. Read more here:
http://en.wikipedia.org/wiki/Kakeya_set
Then I talked about the prisoners-hats puzzle.
You can read more about it here:
http://bekaarbokbok.blogspot.com/2010/07/of-prisoners-and-hats.html
Then Anna presented a very elegant solution of the Fibonnaci problem which I posed in the previous comment (see above) using Mathematical induction.
We then started out talking about the 2009 problem set. We only got to the first problem.
But that is fine. Our goal is not to finish all the problems. We do as many as our time and energy permits.
I handed out the problem set for 2008 Putnam.
We shall focus on this next week.
I also handed out the course announcement for Math 268: Introduction to Undergraduate research in Mathematics which I will be teaching next semester.
P.S: I forgot to mention two more things.
ReplyDeleteI also talked about my blog (under construction)
with the title Ars Longa Vita Brevis. Read about it more here:
http://en.wikipedia.org/wiki/Ars_longa,_vita_brevis
Brian, Amy and I also tried to solve A4 from 2009 but we could not get too far with that. We enjoyed thinking however.