, 2015

We shall prove that the answer is $2n + 2$. Number the rows in increasing order, from top to bottom, and number the columns from left to right. By symmetry, we may (and shall) assume that the turtle starts in the top right corner square.

First we shall prove that some row or column must be entered at least $2n + 2$ times. Let $m = 4n + 2$. First note that each time the turtle moves, she enters either a row or a column. Let $r_i$ denote the number of times the turtle enters row $i$, and let $c_i$ be similarly defined for column $i$. Since the turtle moves $m^2$ times,
$$r_1 + r_2 + \dots + r_m + c_1 + c_2 + \dots + c_m = m^2.$$
Now note that each time the turtle enters column $1$, the next column she enters must be column $2$. Therefore $c_1$ is equal to the number of times the turtle enters column $2$ from column $1$. Furthermore, the turtle must enter column $2$ from column $3$ at least once, which implies that $c_2 > c_1$. Therefore since the $2m$ terms $r_i$ and $c_i$ are not all equal, one must be strictly greater than $m^2/(2m) = 2n + 1$ and therefore at least $2n + 2$.

Now we construct an example to show that it is possible that no row or column is entered more than $2n + 2$ times. Partition the square grid into four $(2n+1) \times (2n+1)$ quadrants $A$, $B$, $C$, and $D$, containing the upper left, upper right, lower left, and lower right corners, respectively. The turtle begins at the top right corner square of $B$, moves one square down, and then moves left through the whole second row of $B$. She then moves one square down and moves right through the whole third row of $B$. She continues in this pattern, moving through each remaining row of $B$ in succession and moving one square down when each row is completed. Since $2n+1$ is odd, the turtle ends at the bottom right corner of $B$. She then moves one square down into $D$ and through each column of $D$ in turn, moving one square to the left when each column is completed. She ends at the lower left corner of $D$ and moves left into $C$ and through the rows of $C$, moving one square up when each row is completed, ending in the upper left corner of $C$. She then enters $A$ and moves through the columns of $A$, moving one square right when each column is completed. This takes her to the upper right corner of $A$, whereupon she enters $B$ and moves right through the top row of $B$, which returns her to her starting point. Each row passing through $A$ and $B$ is entered at most $2n+1$ times in $A$ and once in $B$, and thus at most $2n+2$ times in total. Similarly, each row and column in the grid is entered at most $2n+2$ times by this path. (See figure below.)

Problem 3: the case $n = 3$