Let $n$ be an odd positive integer. Some of the unit squares of an $n\times n$ unit-square board are colored green. It turns out that a chess king can travel from any green unit square to any other green unit squares by a finite series of moves that visit only green unit squares along the way. Prove that it can always do so in at most $\tfrac{1}{2}(n^2-1)$ moves. (In one move, a chess king can travel from one unit square to another if and only if the two unit squares share either a corner or a side.) Proposed by Nikolai Beluhov
Problem
Source: 2020 Cyberspace Mathematical Competition P4, by Nikolai Beluhov
Tags: combinatorics, cyberspace
khina
15.07.2020 05:32
3:30 and got nowhere
MarkBcc168
15.07.2020 05:38
I heard that this problem is proposed by Nikolai Beluhov. Can someone confirm?
khina
15.07.2020 05:40
confirm.
insertionsort
15.07.2020 05:49
Oops, redacted because completely incorrect.
khina
15.07.2020 05:57
@above oh but we don't have solutions i've heard official solution involves tiling. does anyone have the details?
InternetPerson10
15.07.2020 06:17
insertionsort wrote: Assume a spiral of green squares from the upper-left most corner square of a $7 \times 7$ chessboard (which we can label $(0, 0)$) to the square $(4, 2)$ (3rd row, 5th column). Start the king at $(0, 0)$. The only way the king can get to $(4, 2)$, and travel along green squares is using 30 moves (a distance of 31 squares) by traveling along the spiral. As this is more than condition ($\frac{1}{2}(7^2-1)=24$), is the claim false? The king can skip a corner (because the king can move diagonally).
insertionsort
15.07.2020 06:20
Thanks, then that means the bound is perfect for a spiral, because we remove six corners, which is $30 - 6 = 24 = \frac{1}{2}(7^2-1)$.
dgrozev
15.07.2020 17:38
Don't think, it's a hard one. Suppose, on the contrary, there exists a configuration with $m>\frac{1}{2}(n^2-1)$ moves. So we have a path $k_0,k_1,\dots,k_m$ which cannot be shortened. It means $k_0,k_2,k_4,\dots, k_r$ (where $r=m$ or $r=m-1$ depending on the parity of $m$ ) are not adjacent, i.e. the king cannot go between any two of them with one move. It means if we dispose kings in those positions they do not beat each other. It's a pretty well know their number is at most $\lfloor \frac{n^2}{4}\rfloor$ , which brings a contradiction. To prove that fact one can tile the chessboard with $2\times 2$ squares. In any such square only one king is placed.
Hamel
15.07.2020 18:56
dgrozev wrote: Don't think, it's a hard one. Suppose, on the contrary, there exists a configuration with $m>\frac{1}{2}(n^2-1)$ moves. So we have a path $k_0,k_1,\dots,k_m$ which cannot be shortened. It means $k_0,k_2,k_4,\dots, k_r$ (where $r=m$ or $r=m-1$ depending on the parity of $m$ ) are not adjacent, i.e. the king cannot go between any two of them with one move. It means if we dispose kings in those positions they do not beat each other. It's a pretty well know their number is at most $\lfloor \frac{n^2}{4}\rfloor$ , which brings a contradiction. To prove that fact one can tile the chessboard with $2\times 2$ squares. In any such square only one king is placed. $n$ is not divisible by $2$. I think there is more work to be done. Well your claim is false for $3 \cdot 3$, you can actually put $4$ kings. Nikolai won't go down that easily.
dgrozev
15.07.2020 19:24
You're right! It was the first thing I thought of, but apparently it's deeper! My bad! Ok, it's a nice problem then!
Alex_z_Awesome
16.07.2020 02:47
Proves a weaker bound. We consider a shortest path $p$ between two points. Claim: In any row or column, there's at most $n-1$ squares in $p$. Proof: If not, all squares in the row/column are part of $p$. Case 1: $p$ enters the row/column, going to all the squares in it, and then leaves. Then $p$ enters the row/column on one of the squares on the ends. But then we could go diagonal to the square next to the square on the end and shorten $p$. Case 2: $p$ enters the row/column after leaving it. Then we must have two adjacent squares, say $1$ and $2$ such that $p$ traveled to $1$ before leaving and $p$ traveled to $2$ after coming back. Then we could shorten $p$ by going from $1$ to $2$. $\quad \square$ Claim: We either have $p$ has at most $n$ squares in any two adjacent rows or $p$ has at most $n$ squares in any two adjacent columns Proof: Consider two adjacent rows $r_1$ and $r_2$ first, the case for two adjacent columns is similar. Every time $p$ enters $r_1$ or $r_2$, in every column $p$ visits, $p$ can visit only $1$ square from $r_1 \cup r_2$ or else the path can be shortened. The only exception occurs when $p$ visits only $1$ column, in which case $p$ can visit both squares in that column. Furthermore, after $p$ leaves and comes back, it cannot visit any column adjacent to the already visited columns or else the path can be shortened. Combining these insights together, $p$ can only visit more than $n$ squares if $p$ travels to both squares in every other column. In this case, we can apply the same reasoning to every two adjacent columns, except we don't need to worry about this case for the columns because $p$ doesn't have two squares in the same row and adjacent columns. $\quad \square$ Now, considering the first $\frac{n-1}{2}$ pairs of adjacent rows/columns and the last row/column, we have at most $$\frac{n-1}{2}\cdot n + (n-1) = \frac{n^2+n-1}{2}$$squares in our path, so at most $\frac{n^2+n-3}{2}$ moves required.
gnoka
18.07.2020 14:30
insertionsort wrote: Thanks, then that means the bound is perfect for a spiral, because we remove six corners, which is $30 - 6 = 24 = \frac{1}{2}(7^2-1)$.
Attachments:
Idio-logy
21.07.2020 10:30
Since no solutions have been posted yet: I will post the official solution.
We take the center of each unit square; they form a $n\times n$ lattice. Suppose that the point on the bottom-left corner of the lattice corresponds to the point $(0,0)$, and the minimum distance between two points is 1. Connect two points in the lattice if and only if both are green and a king can go from one to the other. It suffices to show that any path $\mathcal{P}$ on the graph has length at most $\frac{n^2-1}{2}$.
We say that a point in the lattice is bad if both of its coordinates are odd, and good otherwise. Call an edge between two good points a good edge. Since every bad point can be adjacent to at most two edges, the number of edges in $\mathcal{P}$ is at most $2X+Y$, where $X$ is the number of bad points in $\mathcal{P}$ and $Y$ is the number of good edges in $\mathcal{P}$. To bound the quantity $2X+Y$, we provide a tiling of the set of points and good edges in the lattice, using two different tiles, type-A and type-B, described as follows:
A type-A tile consists of a bad point $(u,v)$ together with a triangle (which includes both vertices and edges) whose vertices are $(u+1,v)$, $(u,v+1)$ and $(u+1,v+1)$. (Notice that the tile can rotate 90 degrees, so this is only one of the four possible orientations of the tile.)
A type-B tile consists of two bad points $(u-1,v)$ and $(u+1,v)$, together with the other seven points so that the nine points form a $3\times 3$ lattice centered at $(u,v)$. It also includes an edge from $(u,v)$ to the other six good points, as well as an edge from $(u,v+1)$ to $(u\pm 1, v+1)$. (Since the tile can also rotate 90 degrees, this is only one of the four possible orientations of the tile.)
Here is a picture of the two types of tiles, where the black points are good and the green points are bad:
[asy][asy]
size(5cm);
dot((0,0), green);
dot((0,1));
dot((1,1));
dot((1,0));
draw((0,1)--(1,1)--(1,0)--cycle, red);
dot((4,0));
dot((5,0));
dot((6,0));
dot((4,1), green);
dot((5,1));
dot((6,1), green);
dot((4,2));
dot((5,2));
dot((6,2));
draw((4,0)--(6,2)--(4,2)--(6,0), blue);
draw((5,2)--(5,0), blue);
[/asy][/asy]
Claim. A type-A tile can only contain either a bad point or a good edge in $\mathcal{P}$ (but not both). Similarly, a type-B tile can only contain either two bad points, a bad point and a good edge, or two good edges in $\mathcal{P}$.
Proof. Straightforward casework.
Finally, we will make the tiling so that every bad point is covered at least twice, and every good edge is covered at least once. Then by the Claim and double counting,
\[2X+Y \le \#(\text{type-A tiles}) + 2\#(\text{type-B tiles}).\]Now we will present the actual tiling. The tiling is a bit different depending on $n$ modulo 4, but the idea is the same. We take $n=11, 13, 15, 17$ for examples, and the general tiling should be clear from natural generalizations (for formal descriptions, refer to asymptote code).
11[asy][asy]
size(5.5cm);
int n=11;
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
dot((i,j));
}
}
for(int i=0; i<(n-1)/2; ++i){
for(int j=0; j<(n-1)/2; ++j){
dot((2*i+1,2*j+1), green);
}
}
for(int i=0; i<(n+1)/4; ++i){
draw((2*i,2*i)--(2*i+1,2*i)--(2*i,2*i+1)--cycle, red);
draw((n-1-2*i,2*i)--(n-2-2*i,2*i)--(n-1-2*i,2*i+1)--cycle, red);
draw((2*i,n-1-2*i)--(2*i+1,n-1-2*i)--(2*i,n-2-2*i)--cycle, red);
draw((n-1-2*i,n-1-2*i)--(n-2-2*i,n-1-2*i)--(n-1-2*i,n-2-2*i)--cycle, red);
}
for(int i=0; i<(n-3)/4; ++i){
for(int j=0; j<2*i+2; ++j){
path p = ((n-1)/2 - 2 - 2*i + 2*j, (n-1)/2 + 1 + 2*i)--((n-1)/2 - 2*i + 2*j, (n-1)/2 + 3 + 2*i)--((n-1)/2 - 2 - 2*i + 2*j, (n-1)/2 + 3 + 2*i)--((n-1)/2 - 2*i + 2*j, (n-1)/2 + 1 + 2*i);
path q = ((n-1)/2 - 2 - 2*i + 2*j + 1, (n-1)/2 + 1 + 2*i)--((n-1)/2 - 2 - 2*i + 2*j +1, (n-1)/2 + 1 + 2*i+2);
draw(p, blue);
draw(q ,blue);
draw(shift(n-1,0)*(rotate(90)*p),blue);
draw(shift(n-1,0)*(rotate(90)*q),blue);
draw(shift(n-1,n-1)*(rotate(180)*p), blue);
draw(shift(n-1,n-1)*(rotate(180)*q), blue);
draw(shift(0,n-1)*(rotate(270)*p), blue);
draw(shift(0,n-1)*(rotate(270)*q), blue);
}
}
[/asy][/asy]13[asy][asy]
size(6.5cm);
int n=13;
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
dot((i,j));
}
}
for(int i=0; i<(n-1)/2; ++i){
for(int j=0; j<(n-1)/2; ++j){
dot((2*i+1,2*j+1), green);
}
}
for(int i=0; i<(n-1)/4; ++i){
draw((2*i,2*i)--(2*i+1,2*i)--(2*i,2*i+1)--cycle, red);
draw((n-1-2*i,2*i)--(n-2-2*i,2*i)--(n-1-2*i,2*i+1)--cycle, red);
draw((2*i,n-1-2*i)--(2*i+1,n-1-2*i)--(2*i,n-2-2*i)--cycle, red);
draw((n-1-2*i,n-1-2*i)--(n-2-2*i,n-1-2*i)--(n-1-2*i,n-2-2*i)--cycle, red);
}
for(int i=0; i<(n-1)/4; ++i){
for(int j=0; j<2*i+1; ++j){
path p = ((n-1)/2 - 1 - 2*i + 2*j, (n-1)/2 + 2*i)--((n-1)/2 - 2*i + 2*j + 1, (n-1)/2 + 2 + 2*i)--((n-1)/2 - 1 - 2*i + 2*j, (n-1)/2 + 2 + 2*i)--((n-1)/2 - 2*i + 2*j + 1, (n-1)/2 + 2*i);
path q = ((n-1)/2 - 2*i + 2*j, (n-1)/2 + 2*i)--((n-1)/2 - 2*i + 2*j, (n-1)/2 + 2*i+2);
draw(p, blue);
draw(q ,blue);
draw(shift(n-1,0)*(rotate(90)*p),blue);
draw(shift(n-1,0)*(rotate(90)*q),blue);
draw(shift(n-1,n-1)*(rotate(180)*p), blue);
draw(shift(n-1,n-1)*(rotate(180)*q), blue);
draw(shift(0,n-1)*(rotate(270)*p), blue);
draw(shift(0,n-1)*(rotate(270)*q), blue);
}
}
[/asy][/asy]15[asy][asy]
size(7.5cm);
int n=15;
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
dot((i,j));
}
}
for(int i=0; i<(n-1)/2; ++i){
for(int j=0; j<(n-1)/2; ++j){
dot((2*i+1,2*j+1), green);
}
}
for(int i=0; i<(n+1)/4; ++i){
draw((2*i,2*i)--(2*i+1,2*i)--(2*i,2*i+1)--cycle, red);
draw((n-1-2*i,2*i)--(n-2-2*i,2*i)--(n-1-2*i,2*i+1)--cycle, red);
draw((2*i,n-1-2*i)--(2*i+1,n-1-2*i)--(2*i,n-2-2*i)--cycle, red);
draw((n-1-2*i,n-1-2*i)--(n-2-2*i,n-1-2*i)--(n-1-2*i,n-2-2*i)--cycle, red);
}
for(int i=0; i<(n-3)/4; ++i){
for(int j=0; j<2*i+2; ++j){
path p = ((n-1)/2 - 2 - 2*i + 2*j, (n-1)/2 + 1 + 2*i)--((n-1)/2 - 2*i + 2*j, (n-1)/2 + 3 + 2*i)--((n-1)/2 - 2 - 2*i + 2*j, (n-1)/2 + 3 + 2*i)--((n-1)/2 - 2*i + 2*j, (n-1)/2 + 1 + 2*i);
path q = ((n-1)/2 - 2 - 2*i + 2*j + 1, (n-1)/2 + 1 + 2*i)--((n-1)/2 - 2 - 2*i + 2*j +1, (n-1)/2 + 1 + 2*i+2);
draw(p, blue);
draw(q ,blue);
draw(shift(n-1,0)*(rotate(90)*p),blue);
draw(shift(n-1,0)*(rotate(90)*q),blue);
draw(shift(n-1,n-1)*(rotate(180)*p), blue);
draw(shift(n-1,n-1)*(rotate(180)*q), blue);
draw(shift(0,n-1)*(rotate(270)*p), blue);
draw(shift(0,n-1)*(rotate(270)*q), blue);
}
}
[/asy][/asy]17[asy][asy]
size(8.5cm);
int n=17;
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
dot((i,j));
}
}
for(int i=0; i<(n-1)/2; ++i){
for(int j=0; j<(n-1)/2; ++j){
dot((2*i+1,2*j+1), green);
}
}
for(int i=0; i<(n-1)/4; ++i){
draw((2*i,2*i)--(2*i+1,2*i)--(2*i,2*i+1)--cycle, red);
draw((n-1-2*i,2*i)--(n-2-2*i,2*i)--(n-1-2*i,2*i+1)--cycle, red);
draw((2*i,n-1-2*i)--(2*i+1,n-1-2*i)--(2*i,n-2-2*i)--cycle, red);
draw((n-1-2*i,n-1-2*i)--(n-2-2*i,n-1-2*i)--(n-1-2*i,n-2-2*i)--cycle, red);
}
for(int i=0; i<(n-1)/4; ++i){
for(int j=0; j<2*i+1; ++j){
path p = ((n-1)/2 - 1 - 2*i + 2*j, (n-1)/2 + 2*i)--((n-1)/2 - 2*i + 2*j + 1, (n-1)/2 + 2 + 2*i)--((n-1)/2 - 1 - 2*i + 2*j, (n-1)/2 + 2 + 2*i)--((n-1)/2 - 2*i + 2*j + 1, (n-1)/2 + 2*i);
path q = ((n-1)/2 - 2*i + 2*j, (n-1)/2 + 2*i)--((n-1)/2 - 2*i + 2*j, (n-1)/2 + 2*i+2);
draw(p, blue);
draw(q ,blue);
draw(shift(n-1,0)*(rotate(90)*p),blue);
draw(shift(n-1,0)*(rotate(90)*q),blue);
draw(shift(n-1,n-1)*(rotate(180)*p), blue);
draw(shift(n-1,n-1)*(rotate(180)*q), blue);
draw(shift(0,n-1)*(rotate(270)*p), blue);
draw(shift(0,n-1)*(rotate(270)*q), blue);
}
}
[/asy][/asy]
Finally, observe that in all cases there are $4\left \lceil \frac{n-1}{4} \right \rceil$ type-A tiles, and there are $4\left \lfloor \frac{(n-1)^2}{16} \right \rfloor$ type-B tiles, so
\[2X+Y \le \#(\text{type-A tiles}) + 2\#(\text{type-B tiles}) = 4\left \lceil \frac{n-1}{4} \right \rceil + 8 \left \lfloor \frac{(n-1)^2}{16} \right \rfloor = \frac{n^2-1}{2}.\]
Physicsknight
01.08.2020 23:39
Construct the longest possible path. This path will consist of some number of straight all-green segments connected only at the corners and with non-green straight segments between each green segment. The segments must be described because without the separation the path could be shortened by crossing prematurely between the segments, and the segments are straight because a $1\,\text {wide gap} $ is insufficient for the diagonal segments. Thus the straight segments are more space filling. Note that, every corner must have one fewer required move than expected because of the allowed diagonal moves. King can always cut corners, so to speak. The longest possible path without cutting the corners is evidently $n*\frac{(n+1)}{2}+\frac {(n-1)}{2}-1=\frac {(n^2-1)}{2}+n-1$ We used $-1$ because the king's starting square is not a move. Such a path always has at least $2*\frac {(n-1)}{2}=n-1$ corners. Cutting the corners we have $\frac {(n^2-1)}{2}+n-1-(n-1)=\frac {(n^2-1)}{2} $ moves in the longest possible path. It could be solved directly by counting the largest length of a optimal path between two arbitrary cells $A,B$ on the board. The optimal properties and how the king could move. There does not exist $\mathrm{L-turn} $ in that path. Obtain the largest path when it has a spiral shape from the centre to the most outer cell. Total length of the spiral $3(n-2)+2 (n-4)+\hdots+3=n-1+2\sum_1^{(n-2)}=\frac{(n^2-1)}{2} $
pi_quadrat_sechstel
01.12.2020 00:09
Physicsknight wrote:
This path will consist of some number of straight all-green segments connected only at the corners and with non-green straight segments between each green segment.
The segments must be described because without the separation the path could be shortened by crossing prematurely between the segments, and the segments are straight because a $1\,\text {wide gap} $ is insufficient for the diagonal segments. Thus the straight segments are more space filling.
Note that, every corner must have one fewer required move than expected because of the allowed diagonal moves. King can always cut corners, so to speak.
The longest possible path without cutting the corners is evidently $n*\frac{(n+1)}{2}+\frac {(n-1)}{2}-1=\frac {(n^2-1)}{2}+n-1$
We used $-1$ because the king's starting square is not a move.
Such a path always has at least $2*\frac {(n-1)}{2}=n-1$ corners. Cutting the corners we have $\frac {(n^2-1)}{2}+n-1-(n-1)=\frac {(n^2-1)}{2} $ moves in the longest possible path.
We do not know that we can get the longest possible path by cutting corners from an other path.
n_bug
04.01.2023 11:04
See https://arxiv.org/abs/2301.01152. This problem is Theorem 2, proved in Section 4. Then Section 5 has a description of all paths which attain the maximum. Edit: Published in Enumerative Combinatorics and Applications, volume 3, issue 2, 2023, https://doi.org/10.54550/ECA2023V3S2R16.
YaoAOPS
29.06.2024 08:13
New solution? Differs hard from the Beluhov solution but I can't find a fakesolve in it for now. DM me if you can. It also works for two other equality cases found in Beluhov's paper. 50 MOHS sadness.
Claim: WLOG green unit squares form a path.
Proof. If there's a contradiction, fix the path and remove everything else. $\blacksquare$
Then given a path on a chessboard with no $L$s, we want to show it has at most $\frac{1}{2}(n^2 + 1)$ elements.
String a line through the path and consider the line instead.
For each diagonal between two squares, draw a $2 \times 2$ box around them. Then two boxes can only overlap if the diagonals they contain are directly connected. Merge overlapping boxes to get regions (drawn in green).
Then it follows that each region has less than half elements being lines.
Furthermore, a vertical/horizontal lines which is adjacent to a region must be connected to the region through that line.
Then note that the path consists of a bunch of regions connected by horizontal / vertical line.
Then consider the algorithm of taking a horizontal/vertical line, taking the empty cells above/below that line, and putting these empty cells in the same equivalence class as the cell in the line they touch.
[asy][asy]
int W=9; int H=9; for (int i=0; i<=W; ++i) { draw( (i,0)--(i,H), rgb("333333")+dashed ); } for (int i=0; i<=H; ++i) { draw( (0,i)--(W,i), rgb("333333")+dashed ); }
pen p1 = cyan+linewidth(2); pen p3 = green+linewidth(2);
pen pd = red+linewidth(2); pen pnd = gray+linewidth(2);
draw((0.5,8.5)--(4,8.5), p1); draw((4,8.5)--(5,8.5), p1); draw((5, 8.5)--(7.5, 8.5)--(8.5,7.5)--(8.5,1.5)--(7.5,0.5)--(5,0.5), p1); draw((5,0.5)--(4,0.5), p1); draw((4,0.5)--(1.5,0.5)--(0.5,1.5)--(0.5,5.5)--(1.5,6.5)--(4,6.5), p1); draw((4,6.5)--(5,6.5), p1); draw((5,6.5)--(5.5,6.5)--(6.5,5.5)--(6.5,3.5)--(5.5,2.5)--(5,2.5), p1); draw((5,2.5)--(4,2.5), p1); draw((4,2.5)--(3.5,2.5)--(2.5,3.5)--(3.5,4.5)--(4,4.5), p1); draw((4,4.5)--(5,4.5), p1);
draw((0.5,2.5)--(1.5,2.5), pnd); draw((0.5,3.5)--(1.5,3.5), pnd); draw((0.5,4.5)--(1.5,4.5), pnd); draw((0.5,8.5)--(0.5,7.5), pnd); draw((1.5,8.5)--(1.5,7.5), pnd); draw((2.5,8.5)--(2.5,5.5), pnd); draw((3.5,8.5)--(3.5,5.5), pnd); draw((4.5,8.5)--(4.5,0.5), pd); draw((5.5,8.5)--(5.5,7.5), pnd); draw((6.5,8.5)--(6.5,7.5), pnd); draw((2.5,0.5)--(2.5,1.5), pnd); draw((3.5,0.5)--(3.5,1.5), pnd); draw((5.5,0.5)--(5.5,1.5), pnd); draw((6.5,0.5)--(6.5,1.5), pnd); draw((7.5,2.5)--(8.5,2.5), pnd); draw((7.5,3.5)--(8.5,3.5), pnd); draw((5.5,4.5)--(8.5,4.5), pnd); draw((7.5,5.5)--(8.5,5.5), pnd); draw((7.5,6.5)--(8.5,6.5), pnd);
draw((0,0)--(2,0)--(2,2)--(0,2)--cycle, p3); draw((2,2)--(4,2)--(4,5)--(2,5)--cycle, p3); draw((0,5)--(2,5)--(2,7)--(0,7)--cycle, p3); draw((5,5)--(7,5)--(7,7)--(5,7)--cycle, p3); draw((7,7)--(9,7)--(9,9)--(7,9)--cycle, p3); draw((7,0)--(9,0)--(9,2)--(7,2)--cycle, p3); draw((5,2)--(7,2)--(7,4)--(5,4)--cycle, p3);
[/asy][/asy]
These empty cells are never parts of regions, and no empty cell is assigned to both a horizontal line and vertical line by the king problem statement.
At the result of algorithm, we have a partitioning of equivalence classes which consist of alternating cells with lines and empty cells.
Then each equivalence class can only terminate if it hits a region, the edge of the board, or ends on an empty cell. The first and third cases end with an empty cell. As such, each equivalence class has at least the same number of empty cells as cells with lines, unless an equivalence class stretches from the top to the bottom of the board. Call that equivalence class dense (drawn in red, rest are drawn in grey).
If there's at most one dense class, we are done. Else, suppose that there are two dense classes. They must be the same orientation, WLOG let them be vertical.
Claim: All elements between the two dense classes can WLOG be straight connections.
Proof. Let $h_1, \dots, h_n$ be the series of classes from left to right.
Then the series of lines joining the $\frac{n+1}{2}$ elements of $h_1$ on the left and the series of lines joining elements of $h_2$ on the right must consist of $2$ occurences which are just lines and $n-1$ occurences which consist of looping between two green elements of the class.
If we replace all elements between $h_1$ and $h_n$ with horizontal lines, then this preserves the invariant of being a line, as well as at least having the same number of green cells. (This can be proven by repeatedly stripping layers off some given construction). $\blacksquare$
Now, at the end of this, we have $k$ dense classes in a line (drawn in purple). There consists of an $a \times n$ grid and $b \times n$ grid to the left and right of these classes such that $a + b + k = n$.
Let $f(a, t)$ be the minimal number of cells in the $a \times n$ grid with $t$ looping connections which are unused in a matching of green elements with empty elements (connected to the right hand side).
Now, we bound $f(a, t)$ from below. Use the earlier algorithm to get some matching in equivalence classes on the $a \times n$ grid.
For each looping connection, we can take leftmost $2 \times k$ rectangle(s) which consist of two diagonals in opposite directions connected by a potentially zero number of vertical lines / other diagonals (drawn in brown), which face away from the dense classes. These rectangles must be disjoint by definition of being for distinct looping connections.
Define a bump as a rectangle which is flipped and faces toward the dense classes. Now, consider a vertical strip $V$ of cells between two rectangles, such that no other rectangle intersects (drawn in red).
[asy][asy]
int W=9; int H=9; for (int i=0; i<=W; ++i) { draw( (i,0)--(i,H), rgb("333333")+dashed ); } for (int i=0; i<=H; ++i) { draw( (0,i)--(W,i), rgb("333333")+dashed ); }
pen p1 = cyan+linewidth(2); pen p3 = brown+linewidth(2); pen pd = purple+linewidth(2); pen pk = red+linewidth(2);
path p = (0.5,8.5)--(6.5,8.5)--(7.5,7.5)--(6.5,6.5) --(2.5,6.5)--(1.5,5.5)--(2.5,4.5)--(6.5,4.5)--(8.5,2.5) --(6.5,0.5)--(1.5,0.5)--(0.5,1.5)--(1.5,2.5)--(5.5,2.5);
draw(p, p1);
path rect = (0,0)--(2,0)--(2,3)--(0,3)--cycle;
draw(rect, p3); draw(shift(1,4)*rect, p3); draw(shift(7,1)*rect, p3); draw(shift(6,6)*rect, p3); draw((3.1,0.1)--(3.1,8.9)--(5.9,8.9)--(5.9,0.1)--cycle, pd);
draw((1.5,3)--(1.5,4), pk); draw((7.5,4)--(7.5,6), pk);
[/asy][/asy]
Claim: This vertical strip $V$ contains an unused cell in the matching or it is filled by a bump.
Proof. We can check manually that's impossible for all elements of $V$ to be part of a region unless there's a bump or it's the two cases.
Then replace $V$ with a strip $V'$ inside the earlier strip such that $V'$ intersects no regions and is bounded above and below by region.
Then we can check that the element at the top of $V$ can't be assigned to a horizontal equivalence class.
If it's not assigned to a vertical equivalence class, use that cell to suffice. If it is assigned to some vertical equivalence class, then due to not touching any borders that vertical equivalence class must end on two empty cells, so it has an extra empty cell which can be used. $\blacksquare$
Call these bumps that fill a vertical strip special. Note that each special bump requires travelling back towards the dense classes, so if $b$ is the number of special bumps, then there are at least $t + b$ rectangles. We now consider the minimum number of vertical cells. What this boils down to is that if we take $a$ buckets, and for each rectangle put a marble in the two $x$-coordinate it occupies, then there are at least the same number of vertical strips asa the number of marbles minus $a$ such cells minus $b$ such bumps. As such, $f(a, t) \ge 2(t + b) - a - 2b = 2t - a$.
Now, it follows that there are in total $\frac{n-1}{2}$ loops. So if the $a \times n$ region has $t$ loops and the $b \times n$ region has $\frac{n-1}{2} - t$ loops, this gives \[ f(a, t) + f(b, \frac{n-1}{2}-t) \ge 2t - a + 2 \left(\frac{n-1}{2} - t\right) - b = (n - 1) - a - b = k-1 \]excess cells unused.
This gives the fact there's at most one more green cell than nongreen cell, which finishes.
Kingu has graciously made a diagram for another equality case as mentioned in Beluhov's paper.
(Two of the bumps are omitted for convenience of viewing).
[asy][asy]
int W=11; int H=11;
for (int i=0; i<=W; ++i) { draw( (i,0)--(i,H), rgb("333333")+dashed ); }
for (int i=0; i<=H; ++i) { draw( (0,i)--(W,i), rgb("333333")+dashed ); }
pen p1 = cyan+linewidth(2);
pen p3 = brown+linewidth(2);
pen p4 = green+linewidth(2);
pen pd = purple+linewidth(2);
pen pnd = gray+linewidth(2);
pen pk = red+linewidth(2);
//kings path
path p = (0.5, 0.5)--(9.5, 0.5)--(10.5, 1.5)--(10.5, 4.5)--(9.5, 5.5)--(10.5, 6.5)--(10.5, 9.5)--(9.5, 10.5)--(1.5, 10.5)--(0.5, 9.5)--(0.5, 3.5)--(1.5, 2.5)--(7.5, 2.5)--(8.5, 3.5)--(7.5, 4.5)--(3.5, 4.5)--(2.5, 5.5)--(3.5, 6.5)--(7.5, 6.5)--(8.5, 7.5)--(7.5, 8.5)--(2.5, 8.5);
draw(p, p1);
//dense lines
path red1 = (4.5, 10.5)--(4.5, 0.5);
path red2 = (5.5, 10.5)--(5.5, 0.5);
path red3 = (6.5, 10.5)--(6.5, 0.5);
draw(red1, pk);
draw(red2, pk);
draw(red3, pk);
//mathings
path grey1 = (0.5, 0.5)--(0.5, 1.5);
path grey2 = (1.5, 0.5)--(1.5, 1.5);
path grey3 = (2.5, 0.5)--(2.5, 3.5);
path grey4 = (3.5, 0.5)--(3.5, 3.5);
path grey5 = (7.5, 0.5)--(7.5, 1.5);
path grey6 = (8.5, 0.5)--(8.5, 1.5);
path grey7 = (8.5, 10.5)--(8.5, 9.5);
path grey8 = (7.5, 10.5)--(7.5, 9.5);
path grey18 = (3.5, 10.5)--(3.5, 7.5);
path grey19 = (2.5, 10.5)--(2.5, 7.5);
path grey9 = (10.5, 2.5)--(9.5, 2.5);
path grey10 = (10.5, 3.5)--(9.5, 3.5);
path grey11 = (10.5, 7.5)--(9.5, 7.5);
path grey12 = (10.5, 8.5)--(9.5, 8.5);
path grey13 = (0.5, 4.5)--(1.5, 4.5);
path grey14 = (0.5, 5.5)--(1.5, 5.5);
path grey15 = (0.5, 6.5)--(1.5, 6.5);
path grey16 = (0.5, 7.5)--(1.5, 7.5);
path grey17 = (0.5, 8.5)--(1.5, 8.5);
draw(grey1, pnd);
draw(grey2, pnd);
draw(grey3, pnd);
draw(grey4, pnd);
draw(grey5, pnd);
draw(grey6, pnd);
draw(grey7, pnd);
draw(grey8, pnd);
draw(grey9, pnd);
draw(grey10, pnd);
draw(grey11, pnd);
draw(grey12, pnd);
draw(grey13, pnd);
draw(grey14, pnd);
draw(grey15, pnd);
draw(grey16, pnd);
draw(grey17, pnd);
draw(grey18, pnd);
draw(grey19, pnd);
//red rectangles
path rect1 = (2,4)--(2,7)--(4,7)--(4,4)--cycle;
path rect2 = (7,2)--(7,5)--(9,5)--(9,2)--cycle;
path rect3 = (7,6)--(7,9)--(9,9)--(9,6)--cycle;
path rect4 = (9,4)--(9,7)--(11,7)--(11,4)--cycle;
draw(rect1, p3);
draw(rect2, p3);
draw(rect3, p3);
//green rec
path green1 = (9,0)--(11,0)--(11,2)--(9,2)--cycle;
path green2 = (9,9)--(9,11)--(11,11)--(11,9)--cycle;
path green3 = (0,9)--(0,11)--(2,11)--(2,9)--cycle;
path green4 = (0,2)--(2,2)--(2,4)--(0,4)--cycle;
draw(green1, p4);
draw(green2, p4);
draw(green3, p4);
draw(green4, p4);
draw(rect4, p4);
//cells not matched
draw((7.5, 5.5)--(8.5, 5.5), pd);
[/asy][/asy]