(EDIT: These solutions earned me a slot in N1, top 16.)
I solved eight problems on the Putnam last Saturday. Here were the solutions I found during the exam, plus my repaired solution to B3 (the solution to B3 I submitted originally had a mistake).
Some comments about the test. I thought that the A test was mostly very easy: problems A1, A3, A4 were all routine, and problem A5 is a little long-winded but nothing magical. Problem A2 was tricky, and took me well over half the A session. I don’t know anything about A6, but it seems to be very hard.
The B session, on the other hand, was completely bizarre. In my opinion, the difficulty of the problems I did attempt was
1.1. Day A
- Points and are on the same branch of the hyperbola . Point is selected between them maximizing the area of . Show that the area of region bounded by the hyperbola and equals the area of region bounded by the hyperbola and .
- Define , and . Find an odd prime dividing .
- Let where . Compute .
- Let be an odd integer and define
Prove is odd if and only if for some prime .
- Let , , , be real matrices. Prove that if and , have the same characteristic polynomial then .
1.2. Night B
- Let be thrice differentiable. Prove that if has at least five distinct roots then has at least two distinct roots.
- Starting with the list of positive integers , we repeatedly remove the first three elements as well as their sum, giving a sequence of sums , , , , , and so on. Decide whether some sum in the sequence ends with in base .
- Define to be the set of real matrices such that , , , form an arithmetic progression in that order. Find all such that for some integer , .
- Let . Prove that
is rational and determine its value.
- Let be the number of permutations such that where . For any show that
does not depend on and determine its value.
- Let be the number of odd divisors of in the interval . Compute
2. Solution to Problem A1
Standard A1 fare. WLOG is to the left of on the positive branch. First we claim the tangent to must be parallel to line ; otherwise let it intersect the parabola again at , and any point between and will increase the area of . In that case, we must have
Now the area bounded by is
The area of is computed similarly and gives
and so these are equal.
3. Solution to Problem A2
By induction we have . Thus for any , , because their quotient is both rational and an algebraic integer. Thus .
During the test, I only found this solution by computing , \dots, explicitly and factoring the first numbers, upon which I realized .
4. Solution to Problem A3
First, we use the fact that for any odd integer , we have
where is an th root of unity. (Just plug into .) Thus
5. Solution to Problem A4
We first prove that for every . It suffices to consider since otherwise . We note that for any , if and then we require that for some ; since this implies .
Thus among any three consecutive numbers, at least one is in . Plainly and hence .
Finally note that
so the answer is .
6. Solution to Problem A5
Let . By Principle of Inclusion-Exclusion (or Moebius inversion?) we have
The vanishes when taking modulo . Now, depends only on the input modulo , equalling for and for . As the exponents in the floor also can be taken mod . Therefore, we can simplify this to
Let . The solution now proceeds in three cases.
If any prime is or mod , say , then for and thus is even.
If all primes are or mod and , then and for and thus is even.
But if and then is always odd. This completes the proof.
7. Solution to Problem B1
Let . The problem asks to show having five distinct real roots implies has at least two. But by Rolle’s Theorem on
we see that having roots gives having roots, so done. (I’m told the trick of considering this function is not new, though I came up with it during the exam so I can’t verify this.)
Lots of people said something about trying to use the Intermediate Value Theorem to show that has a root between any two roots of . This would require to be continuously differentiable, so it breaks down at the last application to . I deliberately appealed to Rolle’s Theorem because I didn’t trust myself to deal with these real-analytic issues during the exam.
8. Solution to Problem B3
The answer is
for . These work by taking .
Now to see these are the only ones, consider an arithmetic matrix
which is not zero everywhere. Its characteristic polynomial is , with discriminant , so it has two distinct real roots; moreover, since either one of the roots is zero or they are of opposite signs.
Now we can diagonalize by writing
where . By using the fact the diagonal entries have sum equalling the off-diagonal entries, we obtain that
Now if too then the same calculation gives
Let (since ). We appropriately get
and odd. If we get and if we get , which gives the curve of solutions that we claimed. (Unfortunately, during the test I neglected to address , which probably means I will get null marks.)
9. Solution to Problem B4
By the Ravi substitution,
No idea why this was B4; it was by far the easiest problem on the test for me. I knew how to do it in less than a second on seeing it and the rest was just arithmetic. (We use the Ravi substitution all the time on olympiad inequalities, so it’s practically a reflex for me.)
10. Solution to Problem B5
My solution was long and disgusting, so I won’t write out the full details. The idea is to let be the number of permutations in with the additional property that . By casework on the index with (which must be surrounded by or if ) one obtains
Also by more casework one obtains the recursion
From this one obtains
So we know and can compute so a long algebraic computation gives that these differ by .
Also, I swear I’ve seen the exact condition many years ago, back when I was doing high school olympiads. But it was so long ago I don’t remember the source.