Putnam 2015
by BOGTRO, Dec 6, 2015, 10:16 PM
Well, my first experience with the Putnam contest was yesterday, and it was definitely an interesting experience. Beforehand, I didn't really have much idea what to expect; I'd done some "practice" problems with other people, but messing around with problems in a group is very different from working on them individually during a contest. What I did know is that the prerequisite knowledge base would presumably be higher than for high school contests -- in particular, calc and lin alg would probably be making appearances.
Unfortunately, despite 18.701 I'm apparently not very comfortable with lin alg, so I got absolutely nowhere on the one problem that used it. In my defense, this was at least partially because the entire B set was evil and I didn't even read B3 until a couple hours into the test; sadly, this also caused my proof-writing to be... somewhat lacking, so I might end up with three 1s on the three problems I solved on B (darn).
Anyway, these are my solutions, attempting to reconstruct exactly what I wrote on the test. After section A I was very confident since I was pretty sure I had four solid solutions (hopefully this is accurate), so I figured as long as I didn't completely bomb section B I should be in a solid spot to get HM. Unfortunately part A used up all the NT
Section B was much more stressful; I'd been actively hoping there wouldn't be too much calc, but B1 was some annoying diffeq that I didn't really have any good ideas how to approach (other than the coefficients suspiciously looking like
). At least it was a #1 so I could get through it quickly and move on to more interesting problems... or so my reasoning went until half an hour later I had zero progress. So I tried B2 for a while, but got absolutely nowhere, and B3 looked hard, so I floated aimlessly between B1 and B2 for a while while getting more and more frustrated.
Eventually I finished B2 first, using an induction that I wasn't (and still aren't) fully confident in, but I definitely solved the problem so hopefully it'll get a 10- grade. Finally, with about half an hour left, I finally came up with the insight as to how B1 would die, so I finished that with about 20 minutes left. Then I looked at B4, which was definitely the easiest problem of the set (maybe I should have looked at this before...), but time pressure made me butcher the computation at the end, and apparently Putnam is very unforgiving towards irrelevant mistakes so that might get a 1 T.T
Unfortunately, despite 18.701 I'm apparently not very comfortable with lin alg, so I got absolutely nowhere on the one problem that used it. In my defense, this was at least partially because the entire B set was evil and I didn't even read B3 until a couple hours into the test; sadly, this also caused my proof-writing to be... somewhat lacking, so I might end up with three 1s on the three problems I solved on B (darn).
Anyway, these are my solutions, attempting to reconstruct exactly what I wrote on the test. After section A I was very confident since I was pretty sure I had four solid solutions (hopefully this is accurate), so I figured as long as I didn't completely bomb section B I should be in a solid spot to get HM. Unfortunately part A used up all the NT
with (WLOG) 
;
are both positive. Let 
.![$[ABP]$](http://latex.artofproblemsolving.com/4/8/8/48884bc091512a29bd03f48e81ba55152b010e59.png)
over ![$p \in [a,b]$](http://latex.artofproblemsolving.com/7/7/2/772334f666a9afaffefda476a1aa007e5075f423.png)
.![$$[ABP]=\left|\frac{\frac{a}{b}+\frac{b}{p}+\frac{p}{a}-\frac{b}{a}-\frac{p}{b}-\frac{a}{p}}{2}\right|$$](http://latex.artofproblemsolving.com/a/b/2/ab292b460f9af30fe54a7bb2ff7303ffb222d741.png)
since 
is constant with respect to 
,
.
so 
(since 
,
and 
be the projections of 
and 
onto the 
-
is given by![$$[B'BPP']-\int_b^{\sqrt{ab}}\frac{1}{x}$$](http://latex.artofproblemsolving.com/7/b/7/7b78c46aa5ff60916cbd5f06c487f21c8a43475d.png)
Let 
be the projection of 
onto the 
,![$$[A'APP']-\int_{\sqrt{ab}}^{a}\frac{1}{x}$$](http://latex.artofproblemsolving.com/9/7/6/976f079a3d234a78acaaa5c2450fa814b535f541.png)
so it suffices to show 
,
is 
,
.
for some constants 
.
and 
,
.
for any 
.
.
,
.
so 
,
is an odd prime factor of 
.
as 
are the 
.
Similarly, when 
is relatively prime to 
form a complete residue class modulo 
since 
.
.
where 
and 
are relatively prime. Thus
from the lemma above, and![$$\prod_{b=1}^{2015}\left(1+e^{\frac{2\pi abi}{2015}}\right)=\left[\prod_{b=1}^{\frac{2015}{d}}\left(1+e^{\frac{2\pi\frac{a}{d}bi}{\frac{2015}{d}}}\right)\right]^d=2^d$$](http://latex.artofproblemsolving.com/d/1/3/d13b5a8e9fccc76c8bf6db75879ca3a403d7ef03.png)
so
and so we want 
.
which is equal to 
as 
appears either in 
or 
and 
is multiplicative.
,
is even precisely when 
.
suppose now there exists an 
such that 
.
to be odd, and since 
,
.
.
for which 
is odd. Then either 
or 
is one bigger than 
is thus
since we can get arbitrarily close to 
by choosing 
for sufficiently small 
,
is 
.Section B was much more stressful; I'd been actively hoping there wouldn't be too much calc, but B1 was some annoying diffeq that I didn't really have any good ideas how to approach (other than the coefficients suspiciously looking like
). At least it was a #1 so I could get through it quickly and move on to more interesting problems... or so my reasoning went until half an hour later I had zero progress. So I tried B2 for a while, but got absolutely nowhere, and B3 looked hard, so I floated aimlessly between B1 and B2 for a while while getting more and more frustrated.Eventually I finished B2 first, using an induction that I wasn't (and still aren't) fully confident in, but I definitely solved the problem so hopefully it'll get a 10- grade. Finally, with about half an hour left, I finally came up with the insight as to how B1 would die, so I finished that with about 20 minutes left. Then I looked at B4, which was definitely the easiest problem of the set (maybe I should have looked at this before...), but time pressure made me butcher the computation at the end, and apparently Putnam is very unforgiving towards irrelevant mistakes so that might get a 1 T.T
.
.
,
has at least 5 distinct real roots, and so 
has at least 2 distinct real roots. Since 
,
has at least 2 distinct real roots as desired.
as some function of 
equal to the given 
,
and 
were getting absolutely nowhere; quite unsurprisingly in fact, since this wouldn't actually say much about 
,
to give what I wanted. But then 
,
to get the right coefficients. Then we want 
to all be the same; this motivates 
,
,
and 
are in the list of sums. We will prove this by induction. Suppose it holds for all 
.
as well. The base when where 
is clear from quick computation, as 6 is in the list of sums.
be the set of triples 
such that 
are the three smallest remaining numbers at some point in the process. By the inductive hypothesis, 
,
,
are in 
.
,
or 
.
.
and 
are in 
is in the list of sums for any 
,
is in the list of sums for any 
is in the list of sums, so the answer is 
.
.
are positive integers. Furthermore, for any choice of 
where we set 
and 
respectively.
constant. Then we have
Hold 
constant. Then we have
Which is equal to
we decompose into
which is just a product of easily-computable geometric series. I really don't know how I missed this T.T
August 2018
December 2015