MHB Is there a solution to the equation $x^2+2y^2=3z^2$?

[Ackbach]

Here is this week's POTW:

-----

Let $S_0$ be a finite set of positive integers. We define finite sets $S_1,S_2,\ldots$ of positive integers as follows: the integer $a$ is in $S_{n+1}$ if and only if exactly one of $a-1$ or $a$ is in $S_n$. Show that there exist infinitely many integers $N$ for which $S_N=S_0\cup\{N+a: a\in S_0\}$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 269 - Jun 28, 2017

This was Problem B-5 in the 2000 William Lowell Putnam Mathematical Competition.

No one answered this week's POTW. The solution, attributed to Kiran Kedlaya and his associates, follows:

Spoiler

We claim that all integers $N$ of the form $2^k$, with $k$ a positive integer and $N>\max\{S_0\}$, satisfy the desired conditions.

It follows from the definition of $S_n$, and induction on $n$, that
\begin{align*}
\sum_{j \in S_n} x^j &\equiv (1+x) \sum_{j \in S_{n-1}} x^j \\
&\equiv (1+x)^n \sum_{j \in S_0} x^j \pmod{2}.
\end{align*}
From the identity $(x+y)^2 \equiv x^2+y^2 \pmod{2}$ and induction on $n$, we have $(x+y)^{2^n} \equiv x^{2^n} + y^{2^n} \pmod{2}$. Hence if we choose $N$ to be a power of 2 greater than $\max\{S_0\}$, then
\[
\sum_{j \in S_n} \equiv (1+x^N) \sum_{j \in S_0} x^j
\]
and $S_N=S_0\cup\{N+a: a\in S_0\}$, as desired.