In a square grid, for a marked $m \times n$ rectangular grid, what is the largest perimeter of a non-self-intersecting grid polygon, if every side of the polygon is vertical or horizontal?
Let's choose the side of an elementary square of the square grid as a unit. If we start from a point of an arbitrary, non-self-intersecting grid polygon and walk along its perimeter, we will pass through as many grid points as the number of units we have traveled. The number of units traveled is always even, because for every unit we move "upward," we must move the same number "downward," and for every unit we move "right," we must move the same number "left" until we return to the starting point. Therefore, the number of grid points on the perimeter of the grid polygon is always even, and this number is the measure of the perimeter of the grid polygon.

![](https://cdn.mathpix.com/cropped/2024_05_02_acc52b76c4a3f8efe2afg-1.jpg?height=336&width=393&top_left_y=428&top_left_x=541)

Figure 1

![](https://cdn.mathpix.com/cropped/2024_05_02_acc52b76c4a3f8efe2afg-1.jpg?height=350&width=460&top_left_y=435&top_left_x=1017)

Figure 2

The number of all grid points in an $m \times n$ grid rectangle (including the grid points on the perimeter and the internal grid points): $(m+1)(n+1)$, so the perimeter of the grid polygon marked within it—according to the above—can be at most $(m+1)(n+1)$. We need to distinguish two cases: a) at least one of $m$ and $n$ is odd, b) both are even.

In case a), $(m+1)(n+1)$ is even, and—as shown in Figure 1—by forming a "comb" shape along the odd unit side of the rectangle, we can create a grid polygon that passes through every grid point, so its perimeter is $(m+1)(n+1)$.

In case b), $(m+1)(n+1)$ is odd, so the perimeter of the maximum perimeter grid polygon can be at most $(m+1)(n+1)-1$. We will show that in this case, there indeed exists a grid polygon that passes through all grid points except one. For example, leave out one column from the grid rectangle, and draw a grid polygon according to case a) in the remaining rectangle, then attach the omitted column with a "stitch" as shown in Figure 2.

Combining both cases, we can state that the perimeter of the maximum perimeter grid polygon that can be inscribed in an $m \times n$ grid rectangle is

$$
k=(m+1)(n+1)+\frac{(-1)^{(m+1)(n+1)}-1}{2}
$$

Zsombok Zoltán (Budapest, IV., Konyves Kalman g. IV. o. t.)