This is a really lovely problem, but it's extremely challenging to solve, and even to write a sketch (as I've done below), takes a ton of time. It was probably never going to make it into the IMO, but I think it's such a great problem that it deserves some attention. I hope I do it justice here. In my opinion, the main difficulty in this problem is discovering a characterization of the final state of the board. Once it's realized, the proof is quite natural. I suppose it's possible to come up with a proof without discovering the characterization, but that seems to be extremely difficult, requiring very strong intuition. Trying some small cases will reveal that the 'curve' formed by the butterflies is kind of circular, yet not quite. It's certainly pretty 'smooth', and 'almost convex'. Naturally, the comfortable butterflies should be 'bottom-left corners' (precisely, a butterfly with no butterfly to its left in the same row, and no butterfly below it in the same column - we call these vanguards), yet (for $n=3$ and up), not all the vanguards end up comfortable. The ones that aren't, however, can be noted to be precisely those that end up forming 'divot's, or those that end up inside the convex hull. That gives us a strong pointer towards considering the convex hull. From there, we can discover that the gradients of the segments of the convex hull are exactly the elements of the Farey sequence of order $n+1$. We can precisely define this shape. Let $S$ be the elements of the Farey sequence of order $n+1$, besides $0$ and $1$. For each term $\frac p q$, we turn it into an ordered pair $(kp, -kq)$ where $k$ is the largest integer such that neither $kp$ nor $kq$ exceed $n+1$. We can then define a curve beginning at the origin, and adding each of the ordered pairs to the corresponding coordinate in sequence. Finally, we translate the curve upwards such that its final point is on the x-axis. We'll call this the optimal curve. With this pattern in hand, we can begin the proof. Let a set of butterflies be regular if every lattice point above and to the right of a butterfly also contains a butterfly. It's quite easy to show that at each step, the set of butterflies is regular. Hence, from here on, we'll only be working with regular sets of butterflies. Let a 'final state' be a regular set of butterflies, none of which are lonely. We define the optimal state to be the state consisting of all the points on, or above the optimal curve. We now want to show a few things: 1. The optimal state is a final state. Since the optimal curve always goes to the right and downwards, it's not hard to see that any butterfly has at least as many neighbors as a butterfly directly below it or to its left. Hence we just need to show that every vanguard is comfortable or crowded. 1A. Vanguards on the convex hull are comfortable. For any such vanguard $A$, note that every lattice point in its neighborhood to the left and/or below it is unoccupied, and every lattice point to its right and/or above it is occupied. Since these two sets are of equal size, we just need to consider the butterflies in the second and fourth quadrants. If we draw lines connecting $A$ to the previous ($P$) and next ($N$) vanguards on the convex hull, we note that $AN$ has the smallest negative gradient that's larger than that of $PA$ between any two vertices in a lattice grid of sidelength $n+1$. Now consider the remaining points in the neighborhood that we haven't yet dealt with. These form lattice grids of sidelength $n$ in the second and fourth quadrants. Consider any point $C$ in the grid in the second quadrant, and its reflection across $A$, $C'$, which lies in the grid in the fourth quadrant. If the gradient $CA$ is at least that of $PA$, then $C$ is in the optimal state, while the gradient of $AC'$ is less than that of $AN$, and hence $C'$ isn't in the optimal state. Otherwise, by similar logic, $C$ isn't in the optimal state, while $C'$ is. Either way, we pair off the remaining points in the neighborhood, hence $A$ is comfortable. 1A. Vanguards not on the convex hull are crowded. For a vanguard not on the convex hull, $V$, we can consider the nearest vanguards to its left and right that are, say $A$ and $B$ respectively. If $V$ is a neighbor of $A$, then likewise $A$ is a neighbor of $V$. For any other neighbor $N$ of $A$, we claim that the point $N'$ such that $ANN'V$ is a parallelogram is a neighbor of $V$. $N'$ is easily shown to be in the neighborhood of $V$, so we just need to show that it lies above the optimal curve. $N$ must be in the first, second, or fourth quadrants relative to $A$, and $N'$ must be in the same quadrant relative to $V$. In the first two cases, it's not hard to prove. In the final case, consider the next vanguard on the convex hull to the right of $B$ (if this doesn't exist, just take the point $n$ units to he right of $B$), $C$. The gradient of $AN$ must be at least the gradient of $BC$, since it's strictly greater than that of $AB$, and by the definition of the optimal curve, $BC$ has the next smallest possible gradient between pairs of neighbors. Thus, if we draw a parallelogram $VN''CB$, $VN'$ must either be parallel to, or have a shallower gradient than $VN''$, and since $N''$ lies above the optimal curve (this isn't hard to show), $N'$ must too. Thus, $V$ has at least as many neighbors as $A$. Finally, we note that the gradient of $VB$ is greater than that of $AB$, so no neighbor of $A$ could possibly have mapped to $B$ in our process above. However, $B$ is a neighbor of $V$, so $V$ has a strictly greater number of neighbors than $A$. Thus vanguards are comfortable if they are on the convex hull and crowded otherwise, and thus the optimal state is a final state. 2. Every final state is a subset of the optimal state. From an arbitrary final state, we can consider its convex hull. Since it has a greater number of butterflies, any butterflies in its intersection have at least as many neighbors in the convex hull as in the original state, so any butterfly that was in the original state (in particular, every vanguard on the convex hull), must be comfortable or crowded. Consider the broken line formed by its vanguards that lie on its convex hull, running from the y-axis, and ending on the x-axis. Consider the sequence of the gradients of the segments of this broken line. It must be strictly increasing (else the convex hull won't be convex). Consider the division of the negative reals by the gradients of the optimal curve into intervals, like $(-\infty, a_1], (a_1, a_2], ..., (a_n, 0]$. Each gradient must be in the same interval as the previous one, else by a similar argument to how we showed vanguards on the convex hull of the optimal curve are comfortable, we can show that the vanguard in between the two segments is lonely, a contradiction. Consider a section of the broken line which consists of all the segments which have gradient in a particular interval. If we may extend any segment, preserving the gradient, yet keeping the endpoints of the segment on lattice points, such that the entire section lies within a lattice square with sidelength $n+1$, then again by a similar argument we can show that the vanguard at the end of the section is lonely (consider the extended section, show that it is at most comfortable with the extension, and show that the extension increased the neighbor count by at least $1$). From there, we can show that each interval's section has a width and height that are both at least the corresponding width and height of the equivalent segment on the optimal curve. Then, considering the sums of the widths from the start, and the heights from the end, we can show that each of the vanguards bookending each section either corresponds to, or is to the right and/or above the respective one on the optimal curve. Thus, the convex hull, and thus the original final state, is a subset of the optimal state. 3. If a final state ($A$) is a proper subset of another ($B$), the process cannot end in $A$. First, we note that for any given final state $X$, every butterfly in $X$ is present at the start. If, at some time $t$, all butterflies in $X$ are present, then every butterfly in $X$ is at least comfortable, and hence will be present in time $t+1$. Hence, by induction, every butterfly in $X$ will be present when the process terminates. Hence, every butterfly in $B$ will be present when the process terminates, but then so will the butterflies in $B \setminus A$. Hence the process cannot end in $A$. Since every final state is a subset of the optimal state, this means that the process must end in the optimal state. The number of comfortable butterflies in the optimal state is $n^2+1$ Note that if we overlay every segment of the optimal curve such that their upper-left endpoints are at the origin, every lattice point in the square with corners $(-1,-1)$ and $(-(n+1),-(n+1))$ lies on exactly one segment. Each of these points biject to exactly one convex hull vanguard of the optimal state (draw some parallelograms or something), and the extra $1$ comes from the 'starting' vanguard on the y-axis. Hence, the number of comfortable butterflies when the process terminates is $n^2+1$.

The following seems to be true. Quote: Let $A$ be a finite set of lattice points in the fourth quadrant, which is closed leftwards and upwards (essentially a Young tableau with corner at upper-left). Let $S = A \sqcup -A$. Call a butterfly exposed if it has no west or south neighbor. In the Cartesian plane, each lattice point with nonnegative coordinates initially contains a butterfly, and there are no other butterflies. We call a butterfly lonely, crowded, or comfortable, depending on whether the number of butterflies in its $S$-neighborhood is respectively less than, greater than, or equal to $|A|$. Every minute, all exposed lonely butterflies fly away simultaneously. This process goes on for as long as there are any exposed lonely butterflies. Assuming that the process eventually stops, prove the number of exposed comfortable butterflies at the final state equals $|A| + 1$. The original problem is the special case $A = \{1, \dots, n\} \times \{-1, \dots, -n\}$.

Can someone please explain the problem statement.

This was a really hard problem which took me many days to solve. Some ideas in this solution are very difficult to convey precisely, so apologies if the proof is hard to read. I present here a non-constructive proof of a generalized result. The flying process can be replaced with "Every minute, exactly one lonely butterfly flies away, until there are no more lonely butterflies," since a lonely butterfly stays lonely when other butterflies fly away. We now generalize the problem as such. Pick a non-decreasing sequence of positive integers $(a_1,a_2,...,a_k)$ and let $A=\{(-x,y)|1 \leq x \leq k, 1 \leq y \leq a_x \}$. We call such a set a tableau. For a butterfly $(x,y)$, we let its neighbourhood be $(A\cup(-A))+(x,y)$. Then we claim that the process will terminate with exactly $|A|+1$ comfortable butterflies. We call a set $S\in\mathbb{Z}_{\geq 0}^2$ up-right closed if for each $(x,y)\in S$, $(x+1,y)\in S$ and $(x,y+1)\in S$. Note the initial set $\mathbb{Z}_{\geq 0}^2$ is up-right closed. In an up-right closed set $S$, we call a butterfly $(x,y)$ stable if $(x-1,y)$ and $(x,y-1)$ are both not in $S$. Note if $(x,y)\in S$ is lonely, so are $(x-1,y)$ and $(x,y-1)$, if they are in $S$. In particular, there must exist a stable lonely butterfly. The flying process can be replaced with "Every minute, exactly one stable, lonely butterfly flies away, until there are no more lonely butterflies." It should be noted here how this is a generalization to the original problem. For a stable butterfly $(x,y)$, the cell $(x+i,y+j)$ is definitely vacant if $i,j \leq 0$ (not both $0$) and is definitely occupied if $i,j \geq 0$ (not both $0$). Since there are $n^2+2n$ definitely vacant cells and $n^2+2n$ definitely occupied cells, we can ignore those cells without affecting whether the butterfly is lonely, crowded, or comfortable. The reduced neighbourhood corresponds to the tableau $a_1=a_2=...=a_n=n$. We shall now induct on $|A|$. The base case $|A|=1$ has only one possible sequence $a_1=1$ and is trivial. Let $B=\{(-x,y) \in A | x<y\}$ and $B'=\{(x,x+y)|(x,y) \in B\}$. Note that $B'$ is a tableau and $|B'|=|B|<|A|$. By the induction hypothesis, let $S_B$ be the set of butterflies that fly away with the neighbourhood $B' \cup (-B')$ and initial set $\mathbb{Z}_{\geq 0}^2$. Using the earlier argument, it can be seen that if $A'=\{(x,x+y)|(x,y) \in A\}$, then the neighbourhood $A' \cup (-A')$ and initial set $\mathbb{Z}_{\geq 0}^2$ will also have exactly $S_B$ flying away. We apply the shear $f_c(x,y)=(x,y-x+c)$ to the result to obtain that the neighbourhood $A \cup (-A)$ and initial set $\{(x,y)|x \geq 0, x+y \geq c\}$ will have exactly $f_c(S_B)$ flying away for any integer $c$. We repeat the argument with the axes swapped. Let $C=\{(-x,y) \in A | x>y\}$ and $C'=\{(x+y,y)|(x,y) \in C\}$. $S_C$ is the set of butterflies that fly away with the neighbourhood $C' \cup (-C')$ and initial set $\mathbb{Z}_{\geq 0}^2$. Then if $g_c(x,y)=(x-y+c,y)$, the neighbourhood $A \cup (-A)$ and initial set $\{(x,y)|y \geq 0, x+y \geq c\}$ will have exactly $g_c(S_C)$ flying away for any integer $c$. Back to the original setup. Let the neighbourhood be $A \cup (-A)$ and the initial set be $\mathbb{Z}_{\geq 0}^2$. We do the following repeatedly: 1. Consider the smallest integer $c$ such that there is a butterfly $(x,y)$ with $x+y=c$. 2. Let $D=\{(-x,y) \in A | x=y\}$. If there are fewer than $|D|+1$ butterflies with $x+y=c$, all butterflies with $x+y=c$ are trivially lonely and we let them fly away. 3. Otherwise, since the remaining set of butterflies is a subset of both $\{(x,y)|x \geq 0, x+y \geq c\}$ and $\{(x,y)|y \geq 0, x+y \geq c\}$, we can let all butterflies in $f_c(S_B)$ and $g_c(S_C)$ fly away. Let a diagonal be all cells $(x,y)$ with $x+y=c$ for some constant $c$ and let $f_c(S_B)$ and $g_c(S_C)$ contain $\alpha$ and $\beta$ butterflies on the diagonal respectively. Then the first diagonal to not have all butterflies fly away by our process is the one with $c=\alpha + \beta + |D|$. All in all, the butterflies that flew away are (see diagram for example) all $(x,y)$ with $x+y<c$ (green), $f_c(S_B)$ and $g_c(S_C)$ (red) Applying the induction hypothesis, there should be $(|B|+1)+(|C|+1)$ (blue) $+(|D|-1)$ (purple) $=|A|+1$ comfortable butterflies, completing the induction. In particular, the original problem has $|A|=n^2$, so there will be $n^2+1$ comfortable butterflies. $\Box$

Attachments:

The answer is $n^2+1$. We prove the following generalization to Young tableaux. Quote: Let $A$ be a finite set of lattice points in the fourth quadrant that induces a Young tableau. Let $S = A \sqcup -A$. Call a butterfly stable if it has no west or south neighbor. In the Cartesian plane, each lattice point with nonnegative coordinates initially contains a butterfly, and there are no other butterflies. We call a butterfly lonely, crowded, or comfortable, depending on whether the number of butterflies in its $S$-neighborhood is respectively less than, greater than, or equal to $|A|$. Every minute, all stable lonely butterflies fly away simultaneously. This process goes on for as long as there are any stable lonely butterflies. Assuming that the process eventually stops, prove the number of stable comfortable butterflies at the final state equals $|A| + 1$. We prove this via strong induction on $|A|$, with the base case $|A|=1$ trivially true. We call $X$ a location for a set of lattice points if all of the lattice points are in $X$. Partition $A$ into sets $A_{-}$, $A_{0}$, and $A_{+}$ as follows. $A_{-}$ is the set of lattice points in $A$ below the line $y=-x$. $A_{0}$ is the set of lattice points in $A$ on the line $y=-x$. $A_{+}$ is the set of lattice points in $A$ above the line $y=-x$. Let \[ T_{+} = \begin{bmatrix} 1 & 0 \\ -1 & 1 \end{bmatrix}\]and \[ T_{-} = \begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix}.\]Note that $S_{+}(k):=T_{+}A_{+}+\{[0 \ k]^T\}$ (for fixed $k$) is the set of points with location $y \ge 0$ and $y \ge -x+k$ and neighborhood $T_{+}A \: \sqcup \: T_{+}(-A)$ has the same number of flying away butterflies as in the original configuration for $A_{+}$. A similar argument shows that $S_{-}(k):=T_{-}A_{-}+\{[k \ 0]^T\}$ has the same number of flying away butterflies as the original configuration for $A_{-}$. Claim: The stable butterflies that fly away are the lattice points $(x, y)$ with $x+y \le k$ and $(x, y) \in S_{+}(k) \cup S_{-}(k)$, where $k$ is the smallest number satisfying \[ k=|S_{+}(k) \cap \{(x, y): x+y=k\}|+|S_{-}(k) \cap \{(x, y): x+y=k\}|+|A_0|.\]Proof. The smallest $k$ satisfying the above condition is also the smallest $k$ such that the diagonal $x+y=k$ has at least one butterfly that has not flown away (which can be seen by counting the points on $x+y=k$). To obtain the set of stable butterflies that fly away, we use the following process. Start with the empty set, and let $L=\min \: x+y$. Consider the diagonal $\mathcal{D}$ induced by the line $x+y=L$. If the number of butterflies on $\mathcal{D}$ is at most $|A_0|$, then all of the butterflies are lonely and fly away, so append them to the set, and otherwise, append $S_+(L) \cup S_-(L)$ to the set. Repeat the process until it is inapplicable. Clearly this process returns the set of all stable butterflies that fly away. Now for the inductive step, we note that the comfortable butterflies consist of the $|A_{+}|+1$ comfortable butterflies of $A_{+}$; similarly the $|A_{-}|+1$ comfortable butterflies of $A_{-}$; the comfortable butterflies of $A_0$ which have a count of $|A_0|-1$ by the claim, with the first two cases having enumeration justified by the inductive hypothesis. Thus there are a total of \[ (|A_{+}|+1)+(|A_{-}|+1)+(|A_{0}|-1)=|A|+1 \]comfortable butterflies, which completes the induction. Remark: [motivation] After playing a bit with the $n=4$ case (and $n=3$ as well), I saw that the problem was indeed much nicer when generalized to Young tableaux (thanks to CantonMathGuy for the wording of the generalization!), so somehow splitting the Young tableaux and using strong induction was a key idea. The issue is that the inductive step doesn't work out well; in particular, we cannot simply split the figure into several Young tableaux. This lead to the idea of splitting by the means of a line (in this case, $y=-x$). Applying suitable affine transformations (which seemed quite intuitive given 2023 BAMO #5), I was able to find a characterization of the stable butterflies that fly away. Now the inductive step was far more clear; it looked like $$|X|+1=(|X_1|+1)+(|X_2|+1)+(|X_3|-1),$$and here the oddball $X_3$ is the set of points in $X$ that are on $y=-x$. As for my general thoughts on the problem, it seemed very difficult as the square case was centralized and no answer was given. Fortunately, the OTIS formulation of the problem stated the answer on its own, making the problem seem more clear. So all in all, great problem, uses the idea of affine transforms in the geometry of numbers and has a very nice inductive flavor. However the way in which it was stated in its shortlist formulation provided no intuition with how to start, and so I encourage that people who try this problem attempt to go about solving the generalized problem.

I spent about 5 days on this problem, I feel this is not the kind of magical problem, just need a lot of time to discover the answer and the shape. My solution actually used more NT than Combi. First if we spend 1 hour drawing the case of $n=3,$ we will find the shape below: When the process eventually stops, we consider the convex hull of the rest butterflies, and we will guess the slope of each two Neighboring points are arranging from small to big in multi set $[n]\div [n]:=\{a/b:a,b\in [n]\}.$ And we will notice that all of the vertices of the convex hull is comfortable, so we guess, there are $n^2+1$ comfortable butterflies at last, and now is the proof. First we prove what we are constructing stop, and only the vertices on the convex hull are comfortable. For any point on a convex hull, for example $O$ on the above graph, it is comfortable iff the shadow area have no lattice point. but because each different neiboring slope is actually two continuous frac in the Farey sequence, this is correct. For points not as vertice of convex hull, drawing the same graph and we will find the number of point is more than a half, so we are done. Now we only proved this is the smallest shape when the progress stop. It is obvious the point set left are convex. We first prove if we write all the slope in the convex hull as $p/q$ and $\gcd (p,q)=1,$ then $q\le n.$ Otherwise if $q\ge n+1,$ it is well known that there exists a lattice point under the line and $[ABC]=1/2$ ($A,B,C$ are the 3 points), the butterfly in this point had flew away, so there are at least $2n^2+1$ points in the area with no butterfly. However, by $q\ge N+1$ we get there is no lattice point in the above area, so we get contradiction. Now if all the $q\le n,$ that means all the slope are from the $n$-th Farey sequence. Now we only need there should be at least $\lfloor n/q\rfloor$ lines with slope $p/q.$ This is actually quite obvious.$\Box$

Nikolai Beluhov ?