2019 Putnam Problem B1

On Saturday, December 7, 2019, I took the 2019 Putnam competition. The Putnam competition is the premier undergraduate math competition in the United States. It has two sessions of six problems each with 3 hours allotted for each session. The problems are all proof-based and are graded on a 0-10 scale, with 10 points being given only for complete proofs. This exam is infamous for having a median score of 0-1 points out of a total of 120. This was my first time taking the Putnam, so my goal was simply to get a positive score.

According to AoPS, discussion is now allowed on the 2019 Putnam.

Putnam Problem B1 concerns finding the number of squares that can be formed by integer solutions to the equation x^2+y^2 = 2^k. The question reads:

2019 Putnam Problem B1:
Denote by Z^2 the set of all points (x,y) in the plane with integer coordinates. For each integer n>=0, let P_n be the subset of Z^2 consisting of the point (0,0) together with all points (x,y) such that x^2+y^2 = 2^k for some integer k<=n. Determine, as a function of n, the number of four-point subsets of P_n whose elements are the vertices of a square.

This question was a bit of a pain to write up. I’m still not sure if my solution is rigorous enough for the Putnam. Regardless, this was probably the easiest question on the test to solve. Here’s my solution:

Solution #1: Bijection and Induction Approach

I started by showing that there exists a bijection between integer solutions (x,y) to x^2+y^2=n and integer solutions (x’,y’) to x’^2+y’^2 = 2n. It is easy to see that (x’,y’) = (x+y,x-y) works in the forward direction as (x+y)^2+(x-y)^2 = 2x^2+2y^2 = 2n. It is also easy to see that (x,y) = ((x’+y’)/2,(x’-y’)/2) works in the backward direction as x’^2+y’^2 = 2n implies that x’ and y’ have the same parity. It follows that the bijection is complete.

With this bijection, it is easy to show by induction that for exponents k of the form k = 2y, the only solutions are (2^y,0), (0,2^y), (0,-2^y), and (-2^y,0) and for exponents k of the form k = 2y+1, the only solutions are (2^y,2^y), (2^y,-2^y), (-2^y,2^y), and (-2^y,-2^y).

Now, we claim that the answer is 1+5n for all nonnegative integers n. Clearly it is true for n = 0. It suffices to show that for all n, P_n+1 has 5 more squares than P_n. Because adding new points to P_n will not change the number of squares within P_n, it suffices to only count the squares that include the new points. We can notice that these new 4 solutions will always form 5 new squares: one boundary square which connects the 4 points and 4 inner squares which contain one of the new solutions and the origin. To prove that these are the only 5 new squares, it suffices to show that the 4 new solutions form a boundary square and that if a sixth square existed, its points would need to be on the boundary square to form a right angle with one of the boundary points. All squares of this form have already been counted, so indeed, the answer is 1+5n.

As I mentioned above, I am a bit worried about whether this will be rigorous enough for the Putnam graders. It was quite easy to get the right answer, but proving it took quite a while, even if the entire process was relatively trivial. As a side note, it appears that some people were trolled by this question and got the wrong answer 1+n by forgetting the squares with the origin. Regardless, this was still probably the most approachable question this year.

Thanks for reading! See you tomorrow.