I suspect the answer to be $4(n^2-n+1)$ for all $n \in \mathbb N$ and the construction is easy anyway. Maybe there's a way to show that there are at least $4n-4$ squares that are not vertices of the polygon?

Actually, the person who asked me said that nearly half of the students wrote $4n^2-4n+4$, but this is wrong. Try $n=4$

Do you have solutions to this? It's been on here for a few days... I found a construction using 4 turns more than claimed before for $n=4$ and am not sure if it has to do with the parity of $n$. Some trivial observations: the number of vertices of polygon in each row, column must be even; in each of the 2x2's containing the corners of the board there must be a unit square that is not a vertex of a polygon.

Bump this

I can construct $4n^2-2n$ for even $n$.

The answer is $M=4n^2-2n$ for even $n$, and $M=4n^2-2n-2$ for odd $n$. Constructing these could be done inductively. The following is a proof for $M \le 4n^2-2n$ for every $n$ that my friend and I found. I wish someone pushes this bound by $2$ for odd $n$. We prove $M \le 4n^2-2n$ for every $n \ge 1$. Assume that the path formed by the rabbit has $M >4n^2-2n$ vertices. Say a square bad if the rabbit pass it directly, that is, to move without turning directions, and call it good otherwise. If the number of bad squares are $N$, then $M=4n^2-N$, since the only vertices on $\mathcal{P}$ are good squares. Hence $N=4n^2-M<2n$ gives $N \le 2n-1$. We claim the following: Claim 1. Consider the $4n$ row/columns on the $2n \times 2n$ chessboard. If the row/column contains a bad square, then it contains at least $2$ bad squares. Proof of Claim 1. Assume otherwise; WLOG say that some row, say $r$, has only one bad square. There are two cases for the path to pass this bad square: to go horizontally or vertically. Now say that $r$ is adjacent to $r'$ and $r''$ (the upper row and the lower row; if it exists). If we count the edges that connect some square in $r$ and some square in $r' \cup r''$, each good square in row $r$ contributes $1$ edge, whereas the bad square contributes $0$ or $2$ edges. Hence the number edges connecting $r$ and $r' \cup r''$ is $\equiv 2n-1+0 \equiv 1 \pmod 2$. This fact contracts the fact that the path passes each square exactly once. Hence, this row must contain at least two bad squares. $\square$ Now, number the rows by $1,2, \cdots, 2n$ from top to bottom, and number the columns by $1,2, \cdots, 2n$ from left to right. The coordinate of a square lying in row $r$ and column $c$ is $(r,c)$. If a row/column contains no bad squares, say it clean, and dirty otherwise. Since $N \le 2n-1$ and the fact that each dirty rows contain at least $2$ bad squares, there are at most $n-1$ dirty rows. Hence there are at least $n+1$ clean rows. Similarly there are at least $n+1$ clean columns. Now we claim some special properties holds for the clean rows : Claim 2. For each clean row, say, the $r^{th}$ row, the points on the coordinate $(r,2i-1), (r,2i)$ are an edge on the rabbit's path for each $i=1,2, \cdots n$. The similar fact holds for the clean columns. Proof of Claim 2. The $r^{th}$ row contains only good squares. Consider a subgraph of the whole path containing only the squares in the $r^{th}$ row. Since each square is good, the degree of each square in the subgraph is exactly $1$(otherwise the path goes vertically or horizontally at the square). This implies that this subgraph is a perfect matching, and since the only way to pack the $2n$ squares are packing adjacent ones, for every $i$, $(r, 2i-1)$ and $(r,2i)$ are adjacent on the subgraph, as desired. $\square$ Our goal is to find a closed cycle with small length, obtained by connecting the center of each squares on the grid. Especially, in this case, we can find a $2 \times 2$ square in the grid that forms a $1 \times 1$ square in graph terms. Since there are $n+1$ clean rows, by the pigeonhole principle, there exists some $k$ such that the $(2k+1), (2k+2)$-th rows are all clean.(Just pack up the $2n$ rows like $(1,2), (3,4), \cdots $.) Similarly, one can find some $l$ such that the $(2l+1), (2l+2)$-th columns are all clean. Now we consider the $4$ squares by these $2$ rows and $2$ columns. Since the $(2k+1)$-th row is clean, by Claim 2, the squares $(2k+1,2l+1), (2k+1, 2l+2)$ are connected. Repeating this $4$ times gives that the square formed by the squares $(2k+1, 2l+1), (2k+1, 2l+2), (2k+2, 2l+1), (2k+2, 2l+2)$ form a square in graph terms. This contradicts that the rabbit has passed all squares. This contradicts $M>4n^2-2n$, hence $M \le 4n^2-2n$. $\blacksquare$

ThE-dArK-lOrD wrote: I can construct $4n^2-2n$ for even $n$. It does work. The attachment gives the path for n=4. This is the generalized case: Let's consider a 'snake' a walk from 2 adjacent cells to other 2 adjacent cells from the same columns or the same rows that passes through all the cells from these 2 columns (or rows) and changes its direction in all the cells. Take the snake that starts from the most right 2 cells from the first row to the most right 2 cells from the last row. Now consider a 'Neptune's trident' the shape that enters in a $4 \times (2n-2)$ part of the table. (in the attachment there are 2 such, oriented horizontally, in the general case there will be $n/2$ such tridents, oriented the same way). We can stick tridents one to another that have the same orientation and it is very effective, since it leaves very few 'bad' cells. In this way we can construct a walk for the rabbit. Let's compute the number of 'bad' cells. On the second last column there are $2$ such. On the second column there are $n$ such. On the third last column there are $n-2$ bad cells. In total, there will be exactly $2n$ bad cells, so the case works. EDIT: The orange stars in the drawing are the 'bad' cells of the table.

Wrong idea

The lemma is not true; take $$(1,1), (1,3), (2,3), (2,2), (3,2), (3,1)$$.

stroller wrote: Does this argument work for odd $n$? We claim that the number of sides of the chessboard polygon must be $\equiv 0 \pmod 4$ which readily implies the result following the proof given by |mins|, combined with the strengthened claim 1 below which shows that there must be an even number of vertices of the chessboard polygon. Consider filling in the chessboard polygon enclosed by rabbit's path by rectangles starting from some innermost unit square that is adjacent to three sides of the polygon yet not contained within the polygon, the right unit square in the orange shaded rectangle in the attachment for example. Now consider the largest rectangle containing this square and fill it in. This keeps the number of sides $\pmod 4$. Now repeat this operation until the entire figure becomes a $2n-1\times 2n-1$ square. Since no unit squares of the $2n\times 2n$ board are not passed through by the polygon it follows that for each unit square in the $2n-1\times 2n-1$ board circumscribing the chessboard polygon enclosed by the path, all of its 4 vertices must be on the borders or inside the chessboard polygon initially. Thus we can in fact fill the entire board with rectangles in this manner (as the only missing parts are disjoint tunnels formed from rectangles which are made up of unit squares). Strengthened Claim 1: There must be an even number of vertices in each column of the chessboard polygon. Proof: Since rabbit goes along a cycle, rabbit must exit the for the $i$th time before going into the column for the $i+1$th time. Thus we can pair up $i$th time entering and exiting squares and this gives an even number of entering/exiting squares. But these squares are precisely the ones inside the column that are vertices of the chessboard polygon obtained by rabbit's cycle, so our claim is proven. I've heard of a counterexample that has only $26$ vertices on a $6 \times 6$ grid, so the $\pmod 4$ argument doesn't work as far as I know.

lminsl wrote: I've heard of a counterexample that has only $26$ vertices on a $6 \times 6$ grid, so the $\pmod 4$ argument doesn't work as far as I know. Thanks! I missed a case in my casework about filling the rectangles. Wondering if the strengthened claim 1 is true...

lminsl wrote: The answer is $M=4n^2-2n$ for even $n$, and $M=4n^2-2n-2$ for odd $n$. Constructing these could be done inductively. The following is a proof for $M \le 4n^2-2n$ for every $n$ that my friend and I found. I wish someone pushes this bound by $2$ for odd $n$. Sorry for reviving, but can you clarify the inductive construction for odd $n$?

Doesn't an argument of symmetry work here? Divide the $2n\times 2n$ chessboard into four disjoint $n\times n$ chessboards. If one of these smaller chessboards have more vertices than the others, can't the polygon be reconstructed by radial symmetry in relation to the center of the $2n\times 2n$ chessboard (so now every $n\times n$ chessboard have the same number of vertices), forcing the number of vertices on the optimal configuration to be a multiple of four?

Seems like a nice idea. How do you ensure there are no closed loops as a result of reflection? (or maybe I just interpreted it wrong) Could you be more specific about how to construct this by radical symmetry?

@stroller You're correct. This method doesn't work.

To complement joao1's idea, the construction works for $n=2^m$, as Math.Is.Beautiful suggested (check 'moore curves' for hints). I'm thinking of constructions for other values of $n$. P.S. Has anyone thought about the case $(2n+1)\times (2n+1)$? This time the rabbit doesn't necessarily have to pass every square, but it has to come back to the place where it started.

Could somebody post the official solution (if exists) ?

Let $r_i$ denote the $i^{th}$ row, $c_i$ the $i^{th}$ column, $1 \leq i \leq 2n$, and $(i,j)$ the square belonging to the $i^{th}$ row and $j^{th}$ column. Assume that $n \geq 3$ is and odd number and the chessboard has exactly $n$ clean rows and $n$ dirty rows. Assume the same for columns. Also assume that the polygon has $2n$ bad squares, i.e. every dirty row and every dirty column has exactly two bad squares. Lemma 1: let $x_i$ be the horizontal line that separates the row $r_i$ and $r_{i+1}$. Let $y_i$ be the vertical line that separates the column $c_i$ and $c_{i+1}$. Then the polygon intersects each $x_i$ and each $y_i$, $1 \leq i \leq 2n-1$ in an even number of times. Proof: it's clear that this result holds for $x_1$ since the rabbit must leave the row $r_1$ the same number of times it enters this row. Suppose this result does not hold for some $x_k$, $k>1$. Consider the region of the chessboard limited by the lines $x_1$ and $x_k$. Then the rabbit will be trapped inside or outside this region, contradicting the fact that it returns to the start point. Lemma 2: at least one of the squares $(1,2)$ and $(2,1)$ is a bad square. The same holds for each of the following three pairs of squares: $\{(2n-1,1); (2n,2)\}$, $\{(2n,2n-1);(2n-1,2n)\}$, $\{(1,2n-1);(2,2n)\}$. Proof: if this doesn't hold the path of the rabbit will be a unit square. Lemma 3: assume that $n \geq 3$ is odd and the chessboard has exactly $n$ dirty rows and $n$ dirty columns, each of which having two bad squares. Then at least one of the four pairs: $(r_1,r_2)$, $(r_{2n-1},r_{2n})$, $(c_1,c_2)$ and $(c_{2n-1},c_{2n})$ will have exactly two dirty rows or two dirty columns. Proof: assume that the four pairs $(r_1,r_2)$, $(r_{2n-1},r_{2n})$, $(c_1,c_2)$ and $(c_{2n-1},c_{2n})$ have each one dirty row (or column) and one clean row (or column). The case when both of then are clean will be analyzed in lemma 4. We also assumed that every dirty row and every dirty column has exactly two bad squares. Wlog, by lemma 2 let $(2,1)$ be a bad square. Then by our assumption $r_1$ and $c_2$ are clean, $r_2$ and $c_1$ are dirty. Again by lemma 2 it follows that $(2n-1,1)$ and $(2,2n)$ are a bad square. By our assumption on the beggining of this proof and lemma 2 it follows that $r_{2n-1}$ and $c_{2n}$ are dirty, $r_{2n}$ and $c_{2n-1}$ are clean. Since the dirty columns and rows have exactly two bad squares then the path of the rabbit will be resticted only to rows $r_1$, $r_2$, $r_{2n-1}$, $r_{2n}$ and to columns $c_1$, $c_2$, $c_{2n-1}$, $c_{2n}$. (This lemma is much easier to be verified constructing a diagram). Lemma 4: assume that $n \geq 3$ is and odd number and the chessboard has exactly $n$ clean rows and $n$ dirty rows. Assume the same for columns. Then there is $0 \leq i \leq n-1$ such that the rows $r_{2i+1}$ and $r_{2i+2}$ are both clean or the columns $c_{2i+1}$ and $c_{2i+2}$ are both clean. Proof: wlog by lemma 3, $r_1$ and $r_2$ are both dirty. So lemma 4 follows from pigeonhole principle. For the same reason this lemma also follows when the chessboard has $n+1$ clean rows or $n+1$ clean columns. Lemma 5: if $n \geq 3$ is and odd number the chessboard cannot have exactly $n$ clean rows and $n$ dirty rows (the same for columns), each of which having only two bad squares. Proof: by lemma 4, wlog there is $i$ such that $r_{2i+1}$ and $r_{2i+2}$ are both clean. By lemma 2, we cannot have $i=0$ or $i=n-1$. There are segments joining $(2i+1,2j+1)$ and $(2i+1,2j+2)$ and also segments joining $(2i+2,2j+1)$ and $(2i+2,2j+2)$, $0 \leq j \leq n-1$. The path of the rabbit on each clean columns don't intersect $x_{2i}$ or $x_{2i+2}$. The path of the rabbit on each dirty column intersect $x_{2i}$ one time and $x_{2i+2}$ also one time. Since $n$ is odd, the path of the rabbit intersects $x_{2i}$ an odd number of times (the same for $x_{2i+2}$). This contradicts lemma 1.