Let $n$ be a given positive integer. In the Cartesian plane, each lattice point with nonnegative coordinates initially contains a butterfly, and there are no other butterflies. The neighborhood of a lattice point $c$ consists of all lattice points within the axis-aligned $(2 n+1) \times$ $(2 n+1)$ square centered at $c$, apart from $c$ itself. We call a butterfly lonely, crowded, or comfortable, depending on whether the number of butterflies in its neighborhood $N$ is respectively less than, greater than, or equal to half of the number of lattice points in $N$. Every minute, all lonely butterflies fly away simultaneously. This process goes on for as long as there are any lonely butterflies. Assuming that the process eventually stops, determine the number of comfortable butterflies at the final state. (Bulgaria) Answer: $n^{2}+1$.
We always identify a butterfly with the lattice point it is situated at. For two points $p$ and $q$, we write $p \geqslant q$ if each coordinate of $p$ is at least the corresponding coordinate of $q$. Let $O$ be the origin, and let $\mathcal{Q}$ be the set of initially occupied points, i.e., of all lattice points with nonnegative coordinates. Let $\mathcal{R}_{\mathrm{H}}=\{(x, 0): x \geqslant 0\}$ and $\mathcal{R}_{\mathrm{V}}=\{(0, y): y \geqslant 0\}$ be the sets of the lattice points lying on the horizontal and vertical boundary rays of $\mathcal{Q}$. Denote by $N(a)$ the neighborhood of a lattice point $a$. 1. Initial observations. We call a set of lattice points up-right closed if its points stay in the set after being shifted by any lattice vector $(i, j)$ with $i, j \geqslant 0$. Whenever the butterflies form an up-right closed set $\mathcal{S}$, we have $|N(p) \cap \mathcal{S}| \geqslant|N(q) \cap \mathcal{S}|$ for any two points $p, q \in \mathcal{S}$ with $p \geqslant q$. So, since $\mathcal{Q}$ is up-right closed, the set of butterflies at any moment also preserves this property. We assume all forthcoming sets of lattice points to be up-right closed. When speaking of some set $\mathcal{S}$ of lattice points, we call its points lonely, comfortable, or crowded with respect to this set (i.e., as if the butterflies were exactly at all points of $\mathcal{S}$). We call a set $\mathcal{S} \subset \mathcal{Q}$ stable if it contains no lonely points. In what follows, we are interested only in those stable sets whose complements in $\mathcal{Q}$ are finite, because one can easily see that only a finite number of butterflies can fly away on each minute. If the initial set $\mathcal{Q}$ of butterflies contains some stable set $\mathcal{S}$, then, clearly no butterfly of this set will fly away. On the other hand, the set $\mathcal{F}$ of all butterflies in the end of the process is stable. This means that $\mathcal{