Let $P$ be a polygon formed by the edges of an infinite chessboard, which does not intersect itself. Let the numbers $a_1,a_2,a_3$ represent the number of unit squares that have exactly $1,2\text{ or } 3$ edges on the boundary of $P$ respectively. Find the largest real number $k$ such that the inequality $a_1+a_2>ka_3$ holds for each polygon constructed with these conditions.
Problem
Source: Turkey TST 2025 P5
Tags: combinatorics
AlperenINAN
18.03.2025 10:50
That problem has finished my dreams of participating in Imo. I'm glad to know you guys.
AnSoLiN
18.03.2025 15:07
To get many $3$s, first attempt would be to try to have as many side lengths exactly 1 as possible. That can be achieved with a serrated polygon. First shape that comes to mind is
[asy][asy]
size(7cm);
real a = 1.0, b = 1.0;
// int m = 5, n = 5;
// real w = a*m, h = b*n;
// path out = (-1, -1) -- (-1, h+1) -- (w+1, h+1) -- (w+1, -1) -- cycle;
// fill(out, RGB(0, 255, 255));
// draw(out, white);
void fill_cell(int row, int column, Label entry) {
fill((row*a, column*b) -- (row*a+a, column*b) -- (row*a+a, column*b+b) -- (row*a, column*b+b) -- cycle, RGB(80, 80, 255));
label(entry, (row*a+a/2, column*b+b/2), p = fontsize(20pt));
}
void outside_cell(int row, int column, Label entry) {
fill((row*a, column*b) -- (row*a+a, column*b) -- (row*a+a, column*b+b) -- (row*a, column*b+b) -- cycle, RGB(255, 255, 255));
label(entry, (row*a+a/2, column*b+b/2), p = fontsize(20pt));
}
void draw_side_u(int row, int column) {
draw((row*a+a, column*b+b) -- (row*a, column*b+b), RGB(0, 0, 255)+linewidth(2));
}
void draw_side_d(int row, int column) {
draw((row*a, column*b) -- (row*a+a, column*b), RGB(0, 0, 255)+linewidth(2));
}
void draw_side_l(int row, int column) {
draw((row*a, column*b) -- (row*a, column*b+b), RGB(0, 0, 255)+linewidth(2));
}
void draw_side_r(int row, int column) {
draw((row*a+a, column*b+b) -- (row*a+a, column*b), RGB(0, 0, 255)+linewidth(2));
}
outside_cell(0, 0, '1');
outside_cell(0, 1, '3');
outside_cell(-1, 2, '3');
outside_cell(0, 2, '0');
outside_cell(1, 2, '3');
outside_cell(0, 3, '2');
outside_cell(-1, 4, '3');
outside_cell(0, 4, '0');
outside_cell(1, 4, '3');
outside_cell(0, 5, '3');
outside_cell(-2, 0, '0');
outside_cell(-2, 1, '0');
outside_cell(-2, 2, '1');
outside_cell(-2, 3, '0');
outside_cell(-2, 4, '1');
outside_cell(-2, 5, '0');
outside_cell(-2, 6, '0');
outside_cell(-1, 0, '0');
outside_cell(-1, 1, '2');
outside_cell(-1, 3, '3');
outside_cell(-1, 5, '2');
outside_cell(-1, 6, '0');
outside_cell(0, 6, '1');
outside_cell(1, 0, '0');
outside_cell(1, 1, '2');
outside_cell(1, 3, '3');
outside_cell(1, 5, '2');
outside_cell(1, 6, '0');
outside_cell(2, 0, '0');
outside_cell(2, 1, '0');
outside_cell(2, 2, '1');
outside_cell(2, 3, '0');
outside_cell(2, 4, '1');
outside_cell(2, 5, '0');
outside_cell(2, 6, '0');
draw_side_u(-1, 4);
draw_side_d(-1, 4);
draw_side_l(-1, 4);
draw_side_u(1, 4);
draw_side_d(1, 4);
draw_side_r(1, 4);
draw_side_u(0, 5);
draw_side_l(0, 5);
draw_side_r(0, 5);
draw_side_u(0, 0);
draw_side_l(0, 1);
draw_side_r(0, 1);
draw_side_u(-1, 2);
draw_side_d(-1, 2);
draw_side_l(-1, 2);
draw_side_u(1, 2);
draw_side_d(1, 2);
draw_side_r(1, 2);
draw_side_l(0, 3);
draw_side_r(0, 3);
outside_cell(0, 8, '');
[/asy][/asy]
We observe that we can make the number of $+$ shapes more, and get a higher $\frac{a_3}{a_1+a_2}$ ratio. Simple calculation yields that we approach $\frac{4}{3}$. However, thinking we got the example, and proceed to prove $4(a_1+a_2)>3a_3$, we run into a problem, this is not true. Let's call this shape a "spruce tree", and let its height be the number of $+$ shapes it has. Now we will make a "spruce forest" by putting spruce trees side by side with an empty column of width 1 between them. Copying this shape does not change the ratio itself, but by making them share the bad cell between them, we reduce the ratio of bad cells to good cells (bad cell is 1 or 2 while good cell is 3). Finally, we connect them to have a single polygon. Again, simple calculations yield that increasing the number of trees and the tree height, $\frac{a_3}{a_1+a_2}$ approach $2$.
[asy][asy]
size(8cm);
real a = 1.0, b = 1.0;
// int m = 5, n = 5;
// real w = a*m, h = b*n;
// path out = (-1, -1) -- (-1, h+1) -- (w+1, h+1) -- (w+1, -1) -- cycle;
// fill(out, RGB(0, 255, 255));
// draw(out, white);
void fill_cell(int row, int column, Label entry) {
fill((row*a, column*b) -- (row*a+a, column*b) -- (row*a+a, column*b+b) -- (row*a, column*b+b) -- cycle, RGB(80, 80, 255));
label(entry, (row*a+a/2, column*b+b/2), p = fontsize(20pt));
}
void outside_cell(int row, int column, Label entry) {
fill((row*a, column*b) -- (row*a+a, column*b) -- (row*a+a, column*b+b) -- (row*a, column*b+b) -- cycle, RGB(255, 255, 255));
label(entry, (row*a+a/2, column*b+b/2), p = fontsize(20pt));
}
void draw_side_u(int row, int column) {
draw((row*a+a, column*b+b) -- (row*a, column*b+b), RGB(0, 0, 255)+linewidth(2));
}
void draw_side_d(int row, int column) {
draw((row*a, column*b) -- (row*a+a, column*b), RGB(0, 0, 255)+linewidth(2));
}
void draw_side_l(int row, int column) {
draw((row*a, column*b) -- (row*a, column*b+b), RGB(0, 0, 255)+linewidth(2));
}
void draw_side_r(int row, int column) {
draw((row*a+a, column*b+b) -- (row*a+a, column*b), RGB(0, 0, 255)+linewidth(2));
}
outside_cell(0, 0, '2');
outside_cell(1, 0, '2');
outside_cell(2, 0, '2');
outside_cell(3, 0, '2');
outside_cell(4, 0, '2');
outside_cell(0, 1, '2');
outside_cell(-1, 2, '3');
outside_cell(0, 2, '0');
outside_cell(1, 2, '3');
outside_cell(0, 3, '2');
outside_cell(-1, 4, '3');
outside_cell(0, 4, '0');
outside_cell(1, 4, '3');
outside_cell(0, 5, '2');
outside_cell(-1, 6, '3');
outside_cell(0, 6, '0');
outside_cell(1, 6, '3');
outside_cell(0, 7, '3');
outside_cell(4, 1, '2');
outside_cell(3, 2, '3');
outside_cell(4, 2, '0');
outside_cell(5, 2, '3');
outside_cell(4, 3, '2');
outside_cell(3, 4, '3');
outside_cell(4, 4, '0');
outside_cell(5, 4, '3');
outside_cell(4, 5, '2');
outside_cell(3, 6, '3');
outside_cell(4, 6, '0');
outside_cell(5, 6, '3');
outside_cell(4, 7, '3');
outside_cell(-2, -1, '0');
outside_cell(-2, 0, '0');
outside_cell(-2, 1, '0');
outside_cell(-2, 2, '1');
outside_cell(-2, 3, '0');
outside_cell(-2, 4, '1');
outside_cell(-2, 5, '0');
outside_cell(-2, 6, '1');
outside_cell(-2, 7, '0');
outside_cell(-2, 8, '0');
outside_cell(-1, -1, '0');
outside_cell(-1, 0, '1');
outside_cell(-1, 1, '2');
outside_cell(-1, 3, '3');
outside_cell(-1, 5, '3');
outside_cell(-1, 7, '2');
outside_cell(-1, 8, '0');
outside_cell(0, -1, '1');
outside_cell(0, 8, '1');
outside_cell(1, -1, '1');
outside_cell(1, 1, '3');
outside_cell(1, 3, '3');
outside_cell(1, 5, '3');
outside_cell(1, 7, '2');
outside_cell(1, 8, '0');
outside_cell(2, -1, '1');
outside_cell(2, 1, '1');
outside_cell(2, 2, '2');
outside_cell(2, 3, '0');
outside_cell(2, 4, '2');
outside_cell(2, 5, '0');
outside_cell(2, 6, '2');
outside_cell(2, 7, '0');
outside_cell(2, 8, '0');
outside_cell(3, -1, '1');
outside_cell(3, 1, '3');
outside_cell(3, 3, '3');
outside_cell(3, 5, '3');
outside_cell(3, 7, '2');
outside_cell(3, 8, '0');
outside_cell(4, -1, '1');
outside_cell(4, 8, '1');
outside_cell(5, -1, '0');
outside_cell(5, 0, '1');
outside_cell(5, 1, '2');
outside_cell(5, 3, '3');
outside_cell(5, 5, '3');
outside_cell(5, 7, '2');
outside_cell(5, 8, '0');
outside_cell(6, -1, '0');
outside_cell(6, 0, '0');
outside_cell(6, 1, '0');
outside_cell(6, 2, '1');
outside_cell(6, 3, '0');
outside_cell(6, 4, '1');
outside_cell(6, 5, '0');
outside_cell(6, 6, '1');
outside_cell(6, 7, '0');
outside_cell(6, 8, '0');
draw_side_u(0, 7);
draw_side_l(0, 7);
draw_side_r(0, 7);
draw_side_l(4, 1);
draw_side_r(4, 1);
draw_side_u(3, 2);
draw_side_d(3, 2);
draw_side_l(3, 2);
draw_side_u(5, 2);
draw_side_d(5, 2);
draw_side_r(5, 2);
draw_side_l(4, 3);
draw_side_r(4, 3);
draw_side_u(3, 4);
draw_side_d(3, 4);
draw_side_l(3, 4);
draw_side_u(5, 4);
draw_side_d(5, 4);
draw_side_r(5, 4);
draw_side_l(4, 5);
draw_side_r(4, 5);
draw_side_u(3, 6);
draw_side_d(3, 6);
draw_side_l(3, 6);
draw_side_u(5, 6);
draw_side_d(5, 6);
draw_side_r(5, 6);
draw_side_u(4, 7);
draw_side_l(4, 7);
draw_side_r(4, 7);
draw_side_d(0, 0);
draw_side_l(0, 0);
draw_side_u(1, 0);
draw_side_d(1, 0);
draw_side_u(2, 0);
draw_side_d(2, 0);
draw_side_u(3, 0);
draw_side_d(3, 0);
draw_side_d(4, 0);
draw_side_r(4, 0);
draw_side_l(0, 1);
draw_side_r(0, 1);
draw_side_u(-1, 2);
draw_side_d(-1, 2);
draw_side_l(-1, 2);
draw_side_u(1, 2);
draw_side_d(1, 2);
draw_side_r(1, 2);
draw_side_l(0, 3);
draw_side_r(0, 3);
draw_side_u(-1, 4);
draw_side_d(-1, 4);
draw_side_l(-1, 4);
draw_side_u(1, 4);
draw_side_d(1, 4);
draw_side_r(1, 4);
draw_side_l(0, 5);
draw_side_r(0, 5);
draw_side_u(-1, 6);
draw_side_d(-1, 6);
draw_side_l(-1, 6);
draw_side_u(1, 6);
draw_side_d(1, 6);
draw_side_r(1, 6);
[/asy][/asy]
Now we are ready to prove that always $2(a_1+a_2)>a_3$. Call two cells neighbors if they share a common side that also belongs the polygon. A good cell must have at least one bad neighbor, because the middle of its three sides must belong to a bad cell on the other side since polygon can not intersect itself and any vertex belongs to exactly two unit sides. On the other hand, a bad cell is either 1 or 2, so it can have at most two neighbors.If $s$ is the number of (good, bad) neighbor pairs, we get $2(a_1+a_2)\geq s\geq a_3$. Final step is to show that equlity can not hold. For equality to hold, we must have all bad cells have two neighbors, that is they are 2s. However a 1-cell is always present in the figure. Take the highest horizontal line that intersects the polygon. The row just above this line contains a 1. Done. $k$ can at most be $\frac{1}{2}$.