Putnam 2017 (Part 1)

Prologue: it has been some time since I updated my posts (academic workloads…oh dear 😥 ), and why not start with something easier to write?

It’s Putnam season again (December 2). I felt hyped, not really because of me eyeing for the top prizes (aiming for the very top is unrealistic at this point, after all), but because it’s another chance for me to enjoy my mathematical contest wholeheartedly again. Amid the doodling my scratch papers with past-year problems and the problems handed at our problem solving sessions, the day came.

“10, 9, 8, …, 3, 2, 1, Go! Go! Go!” our proctor exclaimed in a bracing way that get us excited for the morning paper, section A.

As I opened the envelope, I was first intrigued by the statement of A1 that shadows many easy Olympiad problems. Not really. I scanned through the problems and A4 came instantly natural to me–so instant that I felt it really artificial (thanks to the problem A3 on the IMO 2016 shortlist, which I used a similar method). Here’s my work on Putnam A4:

(I described this problem in the setting of MATH 245 quiz to my friends, for fun 😛 )

Shortly after my completion of solution writeup was to complete A1, which gave us the relation x in S -> x+5 in S (exercise for readers to prove). Thus all numbers in the form 5k+2 have to be in it (due to condition (i) ). Now 49->54->59->64->…are in S too, which also includes 8->13->18->… (because of 64). Finally we have 54^2->54^2+5->…, and this should be the full list.

No it’s not. Darn it. I was halfway writing through my solution before I realized that. 56^2 is in S so 56 must be too, and this gives 81 -> 9 -> … and 121->11->36->6, so all numbers greater than 1 and not divisible by 5 are in S. I couldn’t believe that my writeup of solution was a mess by then and had to cross out all of them before writing a new solution on the same paper. RIP 😥

The next obvious candidate was A2, which, on its first look, necessitates me to approach by brute force first: try the first few candidates. At n=6 or 7 I noticed that the “supposed polynomial” have coefficients following some binomial pattern, so I tried to prove them. Half and hour into the verification and virtually no progress on it, I realized that this was easier said than done.

Amid my panicking to fight against the time constraint, I realized something fishy: since the polynomial terms followed binomial pattern, why not write it as sum / difference of previous terms using properties of Pascal’s triangle? That’s how I discovered the tricky identity Q_n=xQ_(n-1)-Q_(n-2). That’s the key to the solution, without me being need to continue the tedious and unapproachable binomial work. QED.

30-45 minutes left, and it’d be great if I can kill one more. A3 looked difficult at its first sight, but A5 and A6 aren’t accessible either. With time being too short for quandary, I chose A3 to fight with. First thing into my mind was looking at places where f(x)>g(x), and show that the ratio f^(n+1)/g^n blows up in that area. No. I didn’t know how to make the argument convincing (or rigorous). My best bet was to try out the discrete summation version of the claim that the integral of f^2/g > the integral of f, as below:

See the relation between the two?

But…isn’t the second identity Titu’s lemma? Which can be arranged into Cauchy-Schwarz inequality. Does this mean that the Cauchy-Schwarz inequality can be used for integrals too? 20 minutes left. I didn’t think of verification anymore. Just quote it. As it turned out, I never believed how handy this theorem was when applied to solve this problem. 😀

At that point I didn’t even think of trying A5 and A6 (with < 15 minutes left), so I just had to make sure that my four solutions are good (rumors had that Putnam graders are very harsh with minor mistakes ).  That’s it for section A. I hadn’t heard anyone claiming A5 or A6 in Waterloo, but a few claims of all A1 to A4 like me, with some impressed me with their ingenuous approach to A3 that doesn’t involve any fancy inequality like mine.

How about section B in the afternoon? Stay tuned!

Ps: some trivia-comments on the problems:
A1: “A1 has trap”, said Prof. Kent Merryfield on AoPS. I have already delineated my struggle above with the crossing of my work and ending up writing on the front page “please only read what’s from the bottom of page 2, thank you very much 🙂 ”
A2: oh well, either you see it (Q_n = xQ_(n-1)-Q_(n-2) ) or you don’t. Ugh.
A3: A friend commented “one of the nicest problems because there are many solutions”. Indeed: Prof. Kiran Kedlaya posted 5 solutions to this problems on his website.
A4: Solvable by algorithmic approach (probably the favourite problem by the Computer Science geeks in my class, I guess)
A5: Looks innocent, but turns out really difficult (imagine roots of unity and complex numbers being involved in a probability problem: oh no…)
A6: “To get some ideas, I starred at the Putnam logo on the question paper, which is an icosahedron itself. Doesn’t work,” said one classmate. Laughter followed.