6. A $2^{2014}+1$ by $2^{2014}+1$ grid has some black squares filled. The filled black squares form one or more snakes on the plane, each of whose heads splits at some points but never comes back together. In other words, for every positive integer $n$ greater than 2 , there do not exist pairwise distinct black squares $s_{1}, s_{2}, \ldots, s_{n}$ such that $s_{i}$ and $s_{i+1}$ share an edge for $i=1,2, \ldots, n$ (here $s_{n+1}=s_{1}$ ).
What is the maximum possible number of filled black squares?
Proposed by David Yang.
Answer. If $n=2^{m}+1$ is the dimension of the grid, the answer is $\frac{2}{3} n(n+1)-1$. In this particular instance, $m=2014$ and $n=2^{2014}+1$.
Solution 1. Let $n=2^{m}+1$. Double-counting square edges yields $3 v+1 \leq 4 v-e \leq 2 n(n+1)$, so because $n \not \equiv 1(\bmod 3), v \leq 2 n(n+1) / 3-1$. Observe that if $3 \nmid n-1$, equality is achieved iff (a) the graph formed by black squares is a connected forest (i.e. a tree) and (b) all but two square edges belong to at least one black square.
We prove by induction on $m \geq 1$ that equality can in fact be achieved. For $m=1$, take an "H-shape" (so if we set the center at $(0,0)$ in the coordinate plane, everything but $(0, \pm 1)$ is black); call this $G_{1}$. To go from $G_{m}$ to $G_{m+1}$, fill in $(2 x, 2 y)$ in $G_{m+1}$ iff $(x, y)$ is filled in $G_{m}$, and fill in $(x, y)$ with $x, y$ not both even iff $x+y$ is odd (so iff one of $x, y$ is odd and the other is even). Each "newly-created" white square has both coordinates odd, and thus borders 4 (newly-created) black squares. In particular, there are no new white squares on the border (we only have the original two from $G_{1}$ ). Furthermore, no two white squares share an edge in $G_{m+1}$, since no square with odd coordinate sum is white. Thus $G_{m+1}$ satisfies (b). To check that (a) holds, first we show that $\left(2 x_{1}, 2 y_{1}\right)$ and $\left(2 x_{2}, 2 y_{2}\right)$ are connected in $G_{m+1}$ iff $\left(x_{1}, y_{1}\right)$ and $\left(x_{2}, y_{2}\right)$ are black squares (and thus connected) in $G_{m}$ (the new black squares are essentially just "bridges"). Indeed, every path in $G_{m+1}$ alternates between coordinates with odd and even sum, or equivalently, new and old black squares. But two black squares $\left(x_{1}, y_{1}\right)$ and $\left(x_{2}, y_{2}\right)$ are adjacent in $G_{m}$ iff $\left(x_{1}+x_{2}, y_{1}+y_{2}\right)$ is black and adjacent to $\left(2 x_{1}, 2 y_{1}\right)$ and $\left(2 x_{2}, 2 y_{2}\right)$ in $G_{m+1}$, whence the claim readily follows. The rest is clear: the set of old black squares must remain connected in $G_{m+1}$, and all new black squares (including those on the boundary) border at least one (old) black square (or else $G_{m}$ would not satisfy (b)), so $G_{m+1}$ is fully connected. On the other hand, $G_{m+1}$ cannot have any cycles, or else we would get a cycle in $G_{m}$ by removing the new black squares from a cycle in $G_{m+1}$ (as every other square in a cycle would have to have odd coordinate sum).
This problem and solution were proposed by David Yang.
Solution 2. As above, we can show that there are at most $\frac{2}{3} n(n+1)-1$ black squares. We provide a different construction now for $n=2^{k}+1$.
Consider the grid as a coordinate plane $(x, y)$ where $0 \leq x, y \leq 2^{m}$. Color white the any square $(x, y)$ for which there exists a positive integer $k$ with $x \equiv y \equiv 2^{k-1}(\bmod 2)^{k}$. Then, color white the square $(0,0)$. Color the remaining squares black. Some calculations show that this is a valid construction which achieves $\frac{2}{3} n(n+1)-1$.
This second solution was suggested by Kevin Sun.
Solution 3. We can achieve the bound of $\frac{2}{3} n(n+1)-1$ as above. We will now give a construction which works for all $n=6 k+5$. Let $M=3 k+2$.
Consider the board as points $(x, y)$ where $-M \leq x, y \leq M$. Paint white the following types of squares:
- The origin $(0,0)$ and the corner $(M, M)$.
- Squares of the form $( \pm a, 0)$ and $(0, \pm a)$, where $a \not \equiv 1(\bmod 3)$ and $0<a<M$.
- Any square $( \pm x, \pm y)$ such that $y-x \equiv 0(\bmod 3)$ and $0<x, y<M$.

Paint black the remaining squares. This yields the desired construction.
This third solution was suggested by Ashwin Sah.