Results of Today's Math Competition

[Doom of Doom]

Did anybody else partake in the mathematical competition today?

It was pretty darn hard. Anyway, I'm pretty sure I solved (and these were the ones I turned in):
the one about Alice and Bob's stone game (A2); the sequence problem showing that there were 2005 terms in a row divisible by 2006 (A3); the function that gives a maximum value of another function (B3? I think..); and the one about choosing a subset S of X and integer m (B5?)


Anyway, what'd everybody else think?

I got pretty close on a couple others, I think. I just hope I scored some points...

 

[mattmns]

I probably got a 0

The subset S of X was B2, and I thought m = -(floor of sum of s in S), or m = -(ceiling of sum of s in S), would work for some S in X, but I did not really figure out a way to prove it. What did you do for that one?

 

[0rthodontist]

I took the putnam today also. The ones I handed in at least partial attempts for:
--The donut volume one (A1). It came down to a complicated integral that I couldn't solve, and probably I made a mistake somewhere along the way anyway. I should have spent time checking this more since it was straightforward calculation.
--Alice & Bob. Actually I shouldn't have handed this in, almost guaranteed 0 points.
--the permutation local maxima one. I didn't come up with a definite answer (but learned from another guy during lunch break that the answer is (n+1)/3), but I wrote a recurrence for it. Maybe 1 or 2 points, unless I made a mistake.
--The vector space one with the hypercube. This one seemed pretty simple at first, answer = 2^k and it's easy to find a subspace that intersects the cube at 2^k points. But proving that you can't have more than 2^k intersection points is more difficult--I didn't spend much time on it. Maybe it actually is more than 2^k.
--The one with the sequence limit. 2 pages of rickety calculations coming to an answer of either 0 or divergence (ran out of time before I could look more closely). In the recap afterwards, someone convinced me that it's probably 0.
--The one with the linear partitions. Answer = 1/2 n^2 - 1/2 n + 1, coming from the recurrence an = a(n-1) + n - 1, but my explanation to derive that recurrence is an unrigorous mess. I'm pretty sure my final answer was correct on this since the exam proctor said afterwards it was what he got.

I am very interested in how you did the subset S of X one--I spent about an hour thinking about that without turning in a solution. All I could figure out was that by adjusting m you can assume the x's are between 0 and 1, and I tried to make something like these work:
--the pigeonhole principle (no go)
--some kind of induction on n (tried several, nothing)
--some kind of pseudo-induction where you assume a uniform initial spacing of x's and repeatedly nudge each x by some real amount to arrive at the final spacing

Also Alice & Bob! How?

 

[mattmns]

I figured the permutation one was (n+1)/3 (from just looking at n=2,3,4) but I couldn't get a proof of it either, so I didn't even turn it in.

 

[0rthodontist]

Yeah, I just totally blanked on that one and didn't even try looking at examples. I just went straight to the recurrence and got stuck (the recurrence I got is a(n, k) = (n-2k)a(n-1, k-1), where a(n, k) counts the number of permutations of n numbers that have k local maxima). Maybe I could have solved it if I had found that formula (n+1)/3 from examples, but I just didn't think. For a six hour exam there didn't seem like enough time to even finish the ones I thought I had a shot at.

 

[Doom of Doom]

For a six hour exam there didn't seem like enough time to even finish the ones I thought I had a shot at.

I know how you feel. I only turned in four, and at the end of each three hour session I was scrambling to find more solutions. The torus one, especially (A1). I couldn't solve the integral either, for some reason; I know I got REALLY close, but didn't have enough time to write up another solution for it. Meh. It's done and over. Now it's time to focus on finals!