Problem 1784

The answer is $5n+1$.

We first determine the set $P_n$. Let $Q_n$ be the set of points in $\mathbb{Z}^2$ of the form $(0, \pm 2^k)$ or $(\pm 2^k, 0)$ for some $k \leq n$. Let $R_n$ be the set of points in $\mathbb{Z}^2$ of the form $(\pm 2^k, \pm 2^k)$ for some $k \leq n$ (the two signs being chosen independently). We prove by induction on $n$ that $$P_n = \{(0,0)\} \cup Q_{\lfloor n/2 \rfloor} \cup R_{\lfloor (n-1)/2 \rfloor}.$$ We take as base cases the straightforward computations $$\begin{align*} P_0 &= \{(0,0), (\pm 1, 0), (0, \pm 1)\} \\ P_1 &= P_0 \cup \{(\pm 1, \pm 1)\}. \end{align*}$$ For $n \geq 2$, it is clear that $\{(0,0)\} \cup Q_{\lfloor n/2 \rfloor} \cup R_{\lfloor (n-1)/2 \rfloor} \subseteq P_n$, so it remains to prove the reverse inclusion. For $(x,y) \in P_n$, note that $x^2 + y^2 \equiv 0 \pmod{4}$; since every perfect square is congruent to either 0 or 1 modulo 4, $x$ and $y$ must both be even. Consequently, $(x/2, y/2) \in P_{n-2}$, so we may appeal to the induction hypothesis to conclude.

We next identify all of the squares with vertices in $P_n$. In the following discussion, let $(a,b)$ and $(c,d)$ be two opposite vertices of a square, so that the other two vertices are $$\left( \frac{a-b+c+d}{2}, \frac{a+b-c+d}{2} \right)$$ and $$\left( \frac{a+b+c-d}{2}, \frac{-a+b+c+d}{2} \right).$$

\begin{itemize}
\item Suppose that $(a,b) = (0,0)$. Then $(c,d)$ may be any element of $P_n$ not contained in $P_0$. The number of such squares is $4n$.

\item Suppose that $(a,b), (c,d) \in Q_k$ for some $k$. There is one such square with vertices $$\{(0, 2^k), (0, 2^{-k}), (2^k, 0), (2^{-k}, 0)\}$$ for $k = 0,\dots,\lfloor \frac{n}{2} \rfloor$, for a total of $\lfloor \frac{n}{2} \rfloor + 1$. To show that there are no others, by symmetry it suffices to rule out the existence of a square with opposite vertices $(a,0)$ and $(c,0)$ where $a > \left| c \right|$. The other two vertices of this square would be $((a+c)/2, (a-c)/2)$ and $((a+c)/2, (-a+c)/2)$. These cannot belong to any $Q_k$, or be equal to $(0,0)$, because $|a+c|, |a-c| \geq a - |c| > 0$ by the triangle inequality. These also cannot belong to any $R_k$ because $(a + |c|)/2 > (a - |c|)/2$. (One can also phrase this argument in geometric terms.)

\item Suppose that $(a,b), (c,d) \in R_k$ for some $k$. There is one such square with vertices $$\{(2^k, 2^k), (2^k, -2^k), (-2^k, 2^k), (-2^k, -2^k)\}$$ for $k=0,\dots, \lfloor \frac{n-1}{2} \rfloor$, for a total of $\lfloor \frac{n+1}{2} \rfloor$. To show that there are no others, we may reduce to the previous case: rotating by an angle of $\frac{\pi}{4}$ and then rescaling by a factor of $\sqrt{2}$ would yield a square with two opposite vertices in some $Q_k$ not centered at $(0,0)$, which we have already ruled out.

\item It remains to show that we cannot have $(a,b) \in Q_k$ and $(c,d) \in R_k$ for some $k$. By symmetry, we may reduce to the case where $(a,b) = (0, 2^k)$ and $(c,d) = (2^\ell, \pm 2^\ell)$. If $d>0$, then the third vertex $(2^{k-1}, 2^{k-1} + 2^\ell)$ is impossible. If $d<0$, then the third vertex $(-2^{k-1}, 2^{k-1} - 2^\ell)$ is impossible.

\end{itemize}

Summing up, we obtain $$4n + \left\lfloor \frac{n}{2} \right\rfloor + 1 + \left\lfloor \frac{n+1}{2} \right\rfloor = 5n+1$$ squares, proving the claim.