Putnam 2019

For some time I doubted if I am still going to write about the process of writing a math contest, but since I need some effort to revive this writing page…here it is! (Warning: this is gonna be long)

The session A problem as taken from AoPS

Session A

Part 1 – the warm up

As usual the strategy is to start from the easy problem so I looked at A1, which, unfortunately, wasn’t that easy at its first glance beyond the fact we can factorize the expression into (A+B+C) x (sq(A-B) + sq(B-C) + sq(A-C))/2 (where sq means the square function), which means if A=B=C=0 we get a 0. A few more experimentation: substituting (1, 0, 0) and (1, 1, 0) means we get the value of 1 and 2, respectively. This isn’t taking me anywhere…let’s try A2. Turns out, A2 was quite routine (I was a trigonometry-trick enthusiast back in the IMO times, remember?) To make things more systematic:

1. Notice that the incenter I cuts the angle bisector from C into 2:1,
2. Drop the perpendicular from I to AB to make good use of the arctan condition,
3. Draw parallel to AB from C that intersects the perpendicular line above at D, calculate AD based on the angle beta (double tangent angle formula needed here)
4. Finish off by concluding that alpha = 90 degree

There goes A2 and time to revisit A1. Remember the factorization earlier on? That wasn’t in vain as it turns out: if we make the some of square stay constant at 1 (achievable whenever (A, B, C) are either (k, k, k+1) or (k,k+1, k+1) then we have all the cases for 3k+1 and 3k+2. This idea inspires another solution of 9k via (k-1, k, k+1) and we could just finish off by showing that this expression must be divisible by 9 OR cannot be divisible by 3 (though I should have shown that it must be nonnegative — reason why I lost 2 marks).

Part 2 — strategy and decision

It wasn’t as easy as it sounds because the next candidate wasn’t clear. A6 was out, A4 (differential geometry) wasn’t well under my radar (I was convinced that the answer was no, but no obvious counterexample popped into my mind), so the only clear choices are A3 and…A5? Yet there wasn’t a clear strategy on how to tackle A3 either (for god’s sake how is this an A3?) The only way I could get out from was to invoke AM-GM inequality (M_1)^(2019) >= b_(0)/b_(2019) >= 1/2019 (i.e. this will practically be our lower bound, lol).

There was only around 1 hour and 30 minutes left, so I took a flight instead of a fight and glanced at A5. I tried p=3 (ans=1), p=5 (ans=2) so it looks like the answer has to be (p-1)/2 using the fact that:

1. The i-th derivative of x^k is k(k-1)…(k-i+1)x^(k-i)
2. The highest power of n with (x-1)^n dividing q(x) is the biggest possible M such that q(1), q'(1), …, q(M-1 derivative)(1) are all 0.

But I wasn’t too sure about 2 as it works only for the complex field: who on earth have the expertise on a finite field?!?!?! Chill man…we could very well just verify that: turn out we are all good as long as n < p because (x-1)^p has derivative 0 in prime field. That’s it: for the i-th derivative evaluated at 1 we will just take the following sum:

a_k k(k-1)…(k-i+1)=k^((p+1)/2)(k-1)…(k-i+1)

for k = 1, …, p-1. Finally we remind ourselves that this is a sum of b_i(1^i+…+(p-1)^i), which is divisible by p unless the exponent i is divisible by p-1 (hint: primitive root). Therefore the maximum i we can permit is (p-3)/2 (and therefore the answer is (p-1)/2).

Cool, back to A3. We got the previously-mentioned inequality, we need |z| to be the same for all the roots. There’s how we got the inspiration:

x^(2019)+…+x+1=(x^(2020)-1)/(x-1)

so all roots have size 1. So all it needs to make z=Mx (or is it x/M? Whichever works) and we’re done.

(There’s no part 3, 30 minutes left and I think I better check my work instead of trying A4 or A6).

 

Session B

Part 1: Settle the easy ones first

Contrary to Session A, I looked at the second one (B2) first. The structure of the denominator suggests the use of partial fraction, why not give it a try? And we need the formula:

sq(cos A) – sq(cos B) = (cos A – cos B) (cos A + cos B)

= 4(sin (A+B)/2)(cos (A+B)/2)(sin (B-A)/2)(cos (A-B)/2)

=sin(A+B)sin(B-A)

so each term now becomes 1/sin(pi/2n)(1/sq cos(k pi/2n) – 1/sq cos((k-1) pi/2n)) which gives the convenient telescoping sum, yielding 1/sin(pi/2n)(1/sq(sin pi/2n)^2 – 1) and therefore the limit 8/pi^3 (just take sin(pi/2n) as pi/2n )

Back to viewing B1. It makes an intuitive sense on how to proceed by trying small cases (use infinite descent to show that the points are all in the form (2^m, 2^m), (2^m, 0), (0, 2^m) with its negatives), and I’m 99% sure that the square must either be axis-aligned or have 45 degree difference but proving that became a total nightmare (The most straightforward way is to brute force using “same length” and “perpendicular” criteria but…uh…nobody got time for that).

Part 2: Fight or flight? 

Desperate, I looked at the other problems (3-6) but none seemed too easy (in hindsight it was a mistake not to try B6 since it turned out to be easy). A few scribbling on B3 took me nowhere, so I decided to give B5 a go via small cases (replacing N=1008 with N=2, for example), which gives the next value (after 1, 2, 5) as 10 (because the difference of polynomial degree n is a polynomial degree n – 1), And hey, why can’t we apply the idea to the general case N=1008? What follows is a lot of writing in justifying this argument, finding an expression, and finally, simplifying into what’s required by the problem (which turned out to be F_{2N+2}-F_{N+2}). This last step required a bit of investigation but not too hard after some pattern finding and proof by induction.

Having done B5, the only sensible thing is to revisit B1. It’s an honest struggle, at best, but I finally came up with an argument: if we rotate by 45 degree and shrink It by a factor of sqrt(2) then we’re basically reducing all points from P_n to P_{n-1} and therefore we can continue doing this until at least one point is in P_0 (excluding the origin). Manual check + parity argument means there are only 5 such configurations, and therefore f(n)-f(n-1)=5 for all n. Elegant idea, but my writeup was messy that I was kinda disbelieved to receive a 10/10.

Part 2.1: the final struggle

The last 30 minutes should better be devoted to the problem that I have the strongest feeling about: B3. At this point I couldn’t remember much but all I could remember writing on the solution sheet was pure gibberish . Times up. I gave up.

—