Putnam_2019_B1

Screenshot 2020-05-30 at 11.30.57

consider the first couple n's (and subsequent ones if need be, but i haven’t put them in) to gain an intuition:
P_0=\{(0,0),(1,0),(0,1),(-1,0),(0,-1)\}=\{(0,0),(±1,0),(0,±1)\}
P_1=\{(0,0),(±1,0),(0,±1), (1,±1),(-1,±1)\}

following from this exploration, i claim that P_n can be recursively defined, \forall \ n \geqslant 1, as

\begin{align} P_0&=\{(0,0),(±1,0),(0,±1)\} \\ P_{n} &= \begin{cases} \mbox{$P_{n-1} \cup \{(2^{(n-1)/2},±2^{(n-1)/2}),(-2^{(n-1)/2},±2^{(n-1)/2})\} $}, & \mbox{n odd} \\ \mbox{$P_{n-1} \cup \{(±2^{n/ 2},0),(0,±2^{n/ 2})\} $}, & \mbox{n even} \end{cases} \end{align}

now we must prove this (which is equivalent to proving that the only solutions of x^2+y^2=2^n are as shown in the union set above, for even and odd n respectively)
in x^2+y^2=2^n, we have the sum of two squares on the left. it is well known that squares are either 0,1\pmod4, so we have that x^2+y^2\equiv 0,1,2\pmod4. when n=0, we get the only case of x^2+y^2=2^0\equiv 1\pmod4, where the only solutions will trivially be those found above (in P_0, which coincide with the general solution in the union set in the even case). when n=1, we get the only case of x^2+y^2=2^1\equiv 2\pmod4, where the only solutions will be, again, those found above (in P_1 this time, which coincide with the general solution in the union set in the odd case). when n\geqslant 2 however, we have that 2^n=4\times2^{n-2}\equiv 0\pmod4 \ \forall \ n \implies x^2+y^2\equiv0\pmod4 \iff x^2\equiv y^2\equiv0\pmod4.

splitting the n now into separate odd and even cases, let us first consider when n is odd. (recall we want to prove that the only solutions here are (2^{(n-1)/2},±2^{(n-1)/2}),(-2^{(n-1)/2},±2^{(n-1)/2}))
assume that x^2+y^2=2^k (for some odd k) has solutions (a,b)=(2^{(k-1)/2},±2^{(k-1)/2}),(-2^{(k-1)/2},±2^{(k-1)/2}) only, as the inductive hypothesis.
consider x^2+y^2=2^{k+2}=4(2^k) (next odd number after k is k+2). we can use the inductive hypothesis to obtain x^2+y^2=4(a^2+b^2)=(2a)^2+(2b)^2 which yield the solution (x,y)=(2a,2b). these are unique as a,b are unique (from the hypothesis), and there is no other way to ensure that both x^2,y^2\equiv0\pmod4.
\therefore by induction, noting that this holds for k=1 as proven already, it is now clear that that the proposed solution is unique.

now consider when n is even. (recall we want to prove that the only solutions here are (±2^{n/ 2},0),(0,±2^{n/ 2}))
assume that x^2+y^2=2^k (for some even k) has solutions (a,b)=(±2^{k/ 2},0),(0,±2^{k/ 2}) only, as the inductive hypothesis.
consider x^2+y^2=2^{k+2}=4(2^k) (next even number after k is k+2). very similarly to the odd case, we can use the inductive hypothesis to obtain x^2+y^2=4(a^2+b^2)=(2a)^2+(2b)^2 which yield the solution (x,y)=(2a,2b). these are unique as a,b are unique (from the hypothesis), and there is no other way to ensure that both x^2,y^2\equiv0\pmod4.
\therefore by induction, noting that this holds for k=0, it is now clear that that the proposed solution is unique.

claim: S_k=5k+1, where we let S_k be the number of squares due to 4-point subsets of P_k.

due to the uniqueness of solutions from above, each time n increases by 1, you are adding precisely 4 points to the diagram, in the pattern shown below. in said diagram, when n=0 evidently there is only 1 square (in the centre). when n=1 we have S_1=1+4+1=1+5(1)=6 due to the new big (slanted) square itself and the 4 squares enclosed in it. when n=2 we have S_2=6+1+4=11 due to similar reasoning.
the pattern arises due to the alternating nature of the solutions, when going from even to odd k, and back.

p.s - kind of want to make this last part more rigorous, but can’t rly see how. the pattern is pretty self explanatory due to the previous work

1 Like

:exploding_head: This is special!! :exploding_head:

1 Like