# Putnam exam challenging

1. Dec 2, 2007

### Doom of Doom

Did anyone else toil away for six hours yesterday at the Putnam exam?

I'm fairly confident that I got a couple.
________
A1: Find a where $$y=a x^2 +a x + \frac{1}{24}$$ and $$x=a y^2 +a y + \frac{1}{24}$$ are tangent.

This was easy, once you recognize that the curves could only intersect (i.e. be tangent) along the y=x line.

_____
A2: Find the least possible area of a convex set in the plane that intersects both branches of the hyperbolas xy=1 and xy=-1. (A set S is called convex if for any two points in S the line segment connecting them is contained in S)

It seems obvious to me that this area would be 4, but I spent quite a bit of time on this problem and wasn't able to turn in a good solution for it.

______
A3: Take the integers 1,2,....,(3k+1) and write them down in a random order. What is the probability that, as you write them down, there is no time when the sum of all of the numbers written up to that point is divisible by 3?

If you take all of the numbers and mod them by 3, you get: k+1 ones, k twos and k zeros. Then, if you ignore the zeros (as long as you don't write one in the first position), the only way you can write the one's and two's is like this (and this is easy to show):

1,1,2,1,2,1,2,.....,1,2

So, you can count the number of ways that you can write that out, then count the number of ways that you can insert the zeros into that sequence, and divide out by (3k+1)!.

_______
Those were the problems I got in the first session. The only problem I solved in the second session was B1.

_______
B1: If f(n) is a polynomial with positive integer coefficients, prove that the only case when f(n) divides f(f(n)+1) is when n=1.

This was very easy. All you have to do is mod by f(n), and you get f(n) (mod f(1)) =0 which can only occur when n=1 (because all of the coefficients are positive).

____
B3: Find $$x_{2007}$$ where $$x_0=1$$ and $$x_{n+1}=3x_n+\left\lfloor x_n \sqrt{5}\right\rfloor$$

I didn't turn in a solution for this, and I was never able to get this in closed form, but here is what I reduced it to:

$$x_n=(3+\sqrt{5})^n-(\sqrt{5}-2)\sum_{i=0}^{n-1} x_i$$

_____

That's what I turned in. So, I hope that I get 30 pts. How did everyone else do?

2. Dec 3, 2007

### Diffy

Trying these for fun.

This thing grows fast!
1,5,26,136, 712, 3728, 19520, 102208, 535168, 2802176, 14672384...

x_100 = 7.53313*10^71

3. Dec 3, 2007

### Xevarion

Unfortunately this isn't true (I said the same thing in my solution). It's also possible for them to be tangent at a point where the slope is -1. This gives two additional values of a. :(

4. Dec 4, 2007

### Doom of Doom

Ah. I see that now. I wonder if my answer of a= 2/3, 3/2 will be sufficient to get me any points at all on that problem. For that matter, I wonder how many people tried solving this one and got only two values for a (instead of all four).

5. Dec 4, 2007

### Doom of Doom

However, my solutions for B1 and A3 were pretty much spot on. Now I'm hoping for 20 points. :)

What other problems did you solve?

6. Dec 4, 2007

### Xevarion

Well as I said I did the same thing you did on A1. I think we'll be pretty lucky even to get 1 point for that.

I did A2 and A3 for sure. I also had a proof for A4, but (1) I didn't simplify my answer all the way and (2) I included one extraneous solution. So I'm not going to hope for much.

On B, I had B1 and B2, but for B1 I didn't point out the error in the problem statement (it doesn't work for constant functions). Also I might have made a sign error in my work in B2 (which didn't matter in the end because we take abs value). I don't remember. So it's possible that I won't get much at all on the second half.

I'll be rather disappointed if I get only 20. But I wouldn't be too surprised if I get no more than 2 on all of the ones that aren't perfect.