International Mathematical Olympiad

We always identify a butterfly with the lattice point it is situated at. For two points $p$ and $q$, we write $p⩾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⩾0\}$ and ${\mathcal{R}}_{\mathrm{V}}=\{(0,y):y⩾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⩾0$. Whenever the butterflies form a up-right closed set $\mathcal{S}$, we have $|N(p)\cap \mathcal{S}|⩾|N(q)\cap \mathcal{S}|$ for any two points $p,q\in \mathcal{S}$ with $p⩾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{F}$ is the largest (with respect to inclusion) stable set within $\mathcal{Q}$, and we are about to describe this set.

2. A description of a final set. The following notion will be useful. Let $\mathcal{U}=\{{\vec{u}}_1,{\vec{u}}_2,\dots ,{\vec{u}}_d\}$ be a set of $d$ pairwise non-parallel lattice vectors, each having a positive $x$- and a negative $y$-coordinate. Assume that they are numbered in increasing order according to slope. We now define a $\mathcal{U}$-curve to be the broken line $p_0{p}_1\dots p_d$ such that $p_0\in {\mathcal{R}}_{\mathrm{V}},p_d\in {\mathcal{R}}_{\mathrm{H}}$, and $\overrightarrow{p_{i-1}{p}_i}={\vec{u}}_i$ for all $i=1,2,\dots ,m$ (see the Figure below to the left).



Construction of $\mathcal{U}$-curve



Construction of $\mathcal{D}$

Now, let ${\mathcal{K}}_n=\{(i,j):1⩽i⩽n,-n⩽j⩽-1\}$. Consider all the rays emerging at $O$ and passing through a point from ${\mathcal{K}}_n$; number them as $r_1,\dots ,r_m$ in increasing order according to slope. Let $A_i$ be the farthest from $O$ lattice point in $r_i\cap {\mathcal{K}}_n$, set $k_i=|r_i\cap {\mathcal{K}}_n|$, let ${\vec{v}}_i=\overrightarrow{O{A}_i}$, and finally denote $\mathcal{V}=\{{\vec{v}}_i:1⩽i⩽m\}$; see the Figure above to the right. We will concentrate on the $\mathcal{V}$-curve $d_0{d}_1\dots d_m$; let $\mathcal{D}$ be the set of all lattice points $p$ such that $p⩾p^{\prime }$ for some (not necessarily lattice) point $p^{\prime }$ on the $\mathcal{V}$-curve. In fact, we will show that $\mathcal{D}=\mathcal{F}$.

Clearly, the $\mathcal{V}$-curve is symmetric in the line $y=x$. Denote by $D$ the convex hull of $\mathcal{D}$.

3. We prove that the set $\mathcal{D}$ contains all stable sets. Let $\mathcal{S}\subset \mathcal{Q}$ be a stable set (recall that it is assumed to be up-right closed and to have a finite complement in $\mathcal{Q}$). Denote by $S$ its convex hull; clearly, the vertices of $S$ are lattice points. The boundary of $S$ consists of two rays (horizontal and vertical ones) along with some ${\mathcal{V}}_{\ast }$-curve for some set of lattice vectors ${\mathcal{V}}_{\ast }$.

Claim 1. For every ${\vec{v}}_i\in \mathcal{V}$, there is a ${\vec{v}}_i^{\ast }\in {\mathcal{V}}_{\ast }$ co-directed with $\vec{v}$ with $|{\vec{v}}_i^{\ast }|⩾|\vec{v}|$.

Proof. Let $\ell$ be the supporting line of $S$ parallel to ${\vec{v}}_i$ (i.e., $\ell$ contains some point of $S$, and the set $S$ lies on one side of $\ell$). Take any point $b\in \ell \cap \mathcal{S}$ and consider $N(b)$. The line $\ell$ splits the set $N(b)\backslash \ell$ into two congruent parts, one having an empty intersection with $\mathcal{S}$. Hence, in order for $b$ not to be lonely, at least half of the set $\ell \cap N(b)$ (which contains $2k_i$ points) should lie in $S$. Thus, the boundary of $S$ contains a segment $\ell \cap S$ with at least $k_i+1$ lattice points (including $b$) on it; this segment corresponds to the required vector ${\vec{v}}_i^{\ast }\in {\mathcal{V}}_{\ast }$. $\square$



Claim 2. Each stable set $\mathcal{S}\subseteq \mathcal{Q}$ lies in $\mathcal{D}$.

Proof. To show this, it suffices to prove that the ${\mathcal{V}}_{\ast }$-curve lies in $D$, i.e., that all its vertices do so. Let $p^{\prime }$ be an arbitrary vertex of the ${\mathcal{V}}_{\ast }$-curve; $p^{\prime }$ partitions this curve into two parts, $\mathcal{X}$ (being down-right of $p$) and $\mathcal{Y}$ (being up-left of $p$). The set $\mathcal{V}$ is split now into two parts: ${\mathcal{V}}_{\mathcal{X}}$ consisting of those ${\vec{v}}_i\in \mathcal{V}$ for which ${\vec{v}}_i^{\ast }$ corresponds to segment in $\mathcal{X}$, and a similar part ${\mathcal{V}}_{\mathcal{Y}}$. Notice that the $\mathcal{V}$-curve consists of several segments corresponding to ${\mathcal{V}}_{\mathcal{X}}$, followed by those corresponding to ${\mathcal{V}}_{\mathcal{Y}}$. Hence there is a vertex $p$ of the $\mathcal{V}$-curve separating ${\mathcal{V}}_{\mathcal{X}}$ from ${\mathcal{V}}_{\mathcal{Y}}$. Claim 1 now yields that $p^{\prime }⩾p$, so $p^{\prime }\in \mathcal{D}$, as required. $\square$

Claim 2 implies that the final set $\mathcal{F}$ is contained in $\mathcal{D}$.

4. $\mathcal{D}$ is stable, and its comfortable points are known. Recall the definitions of $r_i$; let $r_i^{\prime }$ be the ray complementary to $r_i$. By our definitions, the set $N(O)$ contains no points between the rays $r_i$ and $r_{i+1}$, as well as between $r_i^{\prime }$ and $r_{i+1}^{\prime }$.

Claim 3. In the set $\mathcal{D}$, all lattice points of the $\mathcal{V}$-curve are comfortable.

Proof. Let $p$ be any lattice point of the $\mathcal{V}$-curve, belonging to some segment $d_i{d}_{i+1}$. Draw the line $\ell$ containing this segment. Then $\ell \cap \mathcal{D}$ contains exactly $k_i+1$ lattice points, all of which lie in $N(p)$ except for $p$. Thus, exactly half of the points in $N(p)\cap \ell$ lie in $\mathcal{D}$. It remains to show that all points of $N(p)$ above $\ell$ lie in $\mathcal{D}$ (recall that all the points below $\ell$ lack this property).

Notice that each vector in $\mathcal{V}$ has one coordinate greater than $n/2$; thus the neighborhood of $p$ contains parts of at most two segments of the $\mathcal{V}$-curve succeeding $d_i{d}_{i+1}$, as well as at most two of those preceding it.

The angles formed by these consecutive segments are obtained from those formed by $r_j$ and $r_{j-1}^{\prime }$ (with $i-1⩽j⩽i+2$) by shifts; see the Figure below. All the points in $N(p)$ above $\ell$ which could lie outside $\mathcal{D}$ lie in shifted angles between $r_j,r_{j+1}$ or $r_j^{\prime },r_{j-1}^{\prime }$. But those angles, restricted to $N(p)$, have no lattice points due to the above remark. The claim is proved. $\square$



Proof of Claim 3

Claim 4. All the points of $\mathcal{D}$ which are not on the boundary of $D$ are crowded.

Proof. Let $p\in \mathcal{D}$ be such a point. If it is to the up-right of some point $p^{\prime }$ on the curve, then the claim is easy: the shift of $N(p^{\prime })\cap \mathcal{D}$ by $\overrightarrow{p^{\prime }p}$ is still in $\mathcal{D}$, and $N(p)$ contains at least one more point of $\mathcal{D}$ - either below or to the left of $p$. So, we may assume that $p$ lies in a right triangle constructed on some hypothenuse $d_i{d}_{i+1}$. Notice here that $d_i,d_{i+1}\in N(p)$.

Draw a line $\ell \parallel d_i{d}_{i+1}$ through $p$, and draw a vertical line $h$ through $d_i$; see Figure below. Let ${\mathcal{D}}_{\mathrm{L}}$ and ${\mathcal{D}}_{\mathrm{R}}$ be the parts of $\mathcal{D}$ lying to the left and to the right of $h$, respectively (points of $\mathcal{D}\cap h$ lie in both parts).



Proof of Claim 4

Notice that the vectors $\overrightarrow{d_{i}p},\overrightarrow{d_{i+1}{d}_{i+2}},\overrightarrow{d_i{d}_{i+1}},\overrightarrow{d_{i-1}{d}_i}$, and $\overrightarrow{p{d}_{i+1}}$ are arranged in non-increasing order by slope. This means that ${\mathcal{D}}_{\mathrm{L}}$ shifted by $\overrightarrow{d_{i}p}$ still lies in $\mathcal{D}$, as well as ${\mathcal{D}}_{\mathrm{R}}$ shifted by $\overrightarrow{d_{i+1}p}$. As we have seen in the proof of Claim 3, these two shifts cover all points of $N(p)$ above $\ell$, along with those on $\ell$ to the left of $p$. Since $N(p)$ contains also $d_i$ and $d_{i+1}$, the point $p$ is crowded. $\square$

Thus, we have proved that $\mathcal{D}=\mathcal{F}$, and have shown that the lattice points on the $\mathcal{V}$-curve are exactly the comfortable points of $\mathcal{D}$. It remains to find their number.

Recall the definition of ${\mathcal{K}}_n$ (see Figure on the first page of the solution). Each segment $d_i{d}_{i+1}$ contains $k_i$ lattice points different from $d_i$. Taken over all $i$, these points exhaust all the lattice points in the $\mathcal{V}$-curve, except for $d_1$, and thus the number of lattice points on the $\mathcal{V}$-curve is $1+{\sum }_{i=1}^m{k}_i$. On the other hand, ${\sum }_{i=1}^m{k}_i$ is just the number of points in ${\mathcal{K}}_n$, so it equals $n^2$. Hence the answer to the problem is $n^2+1$.