Problem A. 887. (October 2024)

A. 887. A non self-intersecting polygon is given in a Cartesian coordinate system such that its perimeter contains no lattice points, and its vertices have no integer coordinates. A point is called semi-integer if exactly one of its coordinates is an integer. Let \(\displaystyle P_1\), \(\displaystyle P_2\), \(\displaystyle \ldots\), \(\displaystyle P_k\) denote the semi-integer points on the perimeter of the polygon. Let \(\displaystyle n_i\) denote the floor of the non-integer coordinate of \(\displaystyle P_i\). Prove that integers \(\displaystyle n_1, n_2, \ldots , n_k\) can be divided into two groups with the same sum.

Proposed by Áron Bán-Szabó, Budapest

(7 pont)

Deadline expired on November 11, 2024.

The basic idea behind this solution is the following: let's count the number of lattice points inside the polygon in two different ways: once grouping them by the horizontal grid lines, once grouping them by the vertical grid lines.

Let's start by focusing on those semi-integer points where the \(\displaystyle x\)-coordinate is integer. We claim that the floor of the \(\displaystyle y\)-coordinates can be summed with appropriate signs to get the number of lattice points in the interior of the polygon. For brevity let \(\displaystyle f(P)\) denote the floor of the non-integer coordinate of a semi-integer point.

To prove this statement let's walk around the perimeter of the polygon in the anti-clockwise direction. If a semi-integer point with an integer \(\displaystyle x\)-coordinate is on a side on which we travel from the left to the right, we choose the plus sign, and if we travel from the right to the left, we choose the negative sign (note that a side containing a point with an integer \(\displaystyle x\)-coordinate cannot be vertical, because the endpoints of such a side would be a semi-integer vertices of the polygon, which was not allowed). Now consider a vertical grid line that intersects our polygon in points \(\displaystyle A_1\), \(\displaystyle A_2\),..., \(\displaystyle A_{2k}\) (from bottom to top). The number of intersections is even, since the polygon alternately crosses the chosen grid line from the left to the right and from the right to the left (since a grid line cannot travel through a vertex of the polygon). Now we claim that \(\displaystyle -f(A_1)+f(A_2)-f(A_3)+...\) counts the number of lattice points on the chosen grid line inside our polygon.

First observe that line segment \(\displaystyle A_{2i-1}A_{2i}\) is inside the polygon, while \(\displaystyle A_{2i}A_{2i+1}\) is outside the polygon. And then we only have to observe that \(\displaystyle f(A_{2i})-f(A_{2i-1})\) is exactly the number of lattice points on line segment \(\displaystyle A_{2i-1}A_{2i}\) (this is even true if \(\displaystyle A_{2i}\) is a lattice point, only \(\displaystyle A_{2i-1}\) has to be a semi-integer point).

Now in the signed sum we have considered every semi-integer point with integer \(\displaystyle x\)-coordinate exactly once, and we have also counted every lattice point inside the polygon exactly one, thus we have proved our statement.

Now we can prove an analogous statement for the semi-integer points with integer \(\displaystyle y\)-coordinates: if \(\displaystyle P\) is such a point, let \(\displaystyle f(P)\) appear in the sum with the negative sign if we go through \(\displaystyle P\) downwards, and let it appear in the sum with the positive sign if we go through \(\displaystyle P\) upwards. Once again, the signed sum of the \(\displaystyle f\) values will be equal to the number of lattice points inside the polygon.

Finally, these two sums are equal to each other, and every semi-integer point appears on exactly one side of the equality (based on whether its \(\displaystyle x\) or \(\displaystyle y\) coordinate is integer; since we have no lattice points on the perimeter, this is uniquely determined). Now adding the negative terms to the other side we get the statement we wanted to prove.

Statistics:

21 students sent a solution.
7 points:	Aravin Peter, Bodor Mátyás, Bui Thuy-Trang Nikolett, Czanik Pál, Forrai Boldizsár, Gyenes Károly, Hodossy Réka, Holló Martin, Keresztély Zsófia, Kocsis 827 Péter, Sánta Gergely Péter, Szakács Ábel, Varga Boldizsár, Virág Tóbiás, Wágner Márton.
6 points:	Morvai Várkony Albert, Tianyue DAI, Vámosi Bendegúz Péter, Vödrös Dániel László.
3 points:	1 student.
2 points:	1 student.

Problems in Mathematics of KöMaL, October 2024