Let $f_0$ be the function from $\mathbb{Z}^2$ to $\{0,1\}$ such that $f_0(0,0)=1$ and $f_0(x,y)=0$ otherwise. For each positive integer $m$, let $f_m(x,y)$ be the remainder when \[ f_{m-1}(x,y) + \sum_{j=-1}^{1} \sum_{k=-1}^{1} f_{m-1}(x+j,y+k) \] is divided by $2$. Finally, for each nonnegative integer $n$, let $a_n$ denote the number of pairs $(x,y)$ such that $f_n(x,y) = 1$. Find a closed form for $a_n$. Proposed by Bobby Shen
Problem
Source: ELMO 2014 Shortlist C6, by Bobby Shen
Tags: function, combinatorics proposed, combinatorics
25.08.2017 18:30
Any solution.
25.08.2017 20:49
Very similar to https://oeis.org/A071053. This is a cellular automaton. Here are the rules. All lattice points can either be activated(on), or deactivated(off). A neighbor $(x,y)$ of a lattice point $(m,n)$ is a different point such that $|x-m|, |y-n| \leq 1$. To go from step $m$ to $m+1$, the following happens: If a cell is deactivated, it will be activated if it has an odd number of neighbors. If a cell is activated, it will be deactivated if it has an even number of neighbors. Only the point $(0, 0)$ is activated on step $0$. Unless this has a nice pattern, it isn't gonna be easy. Not sure how to count this... (It's not exactly the right picture due to some weird integer offset)
Attachments:

15.04.2019 16:46
Trivially $a_n$ equals the number of non-zero terms of $f_n(x,y)=[(x+\frac{1}{x}+1)(y+\frac{1}{y}+1)-1]^n$ in $F_2$. By manipulting functions, we have $\forall k,t\in N$, $0\le i\le 2^{k-1}-1$, $a_{t\cdot 2^k+i}=a_{t}\cdot a_{i}$. This means that if there is a $0$ in $n$'s binary expression, we could cut the expression in two parts and compute them instead. (For example, $a_{(101101110011)_2}=a_{(1011)_2}\cdot a_{(1110011)_2}$.) Thus the problem reduces to finding $a_{2^k-1}$ for all $k\in N$. Since $f_{2^{k+1}-1}=[(x^{2^k}+\frac{1}{x^{2^k}}+1)(y^{2^k}+\frac{1}{y^{2^k}}+1)-1]\cdot f_{2^k-1}$ (in $F_2$ of course), the value matrix of $f_{2^{k+1}-1}$ is equal to the sum of some $8$ tranlations of that of $f_{2^{k}-1}$. A (not) simple reduction would show that $a_{2^k-1}=\frac{5\cdot 4^k+(-2)^{k+1}}{3}$ (it satisfies a second-order linear recurrence with constant coefficients). Combining this with the above claim and we get the desired result. (Unless I'm very mistaken, this is not a closed form in terms of $n$, since it might need arbitrarily many steps of calculation. Anyway, I believe it's the simplest expression- if I didn't get wrong in the induction step.)