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.