ABCDE wrote: if equality holds, then it must enter every row and column exactly $2n+1$ times Could anyone explain this for me please. Edited: OK, I just found the official solution: https://cms.math.ca/Competitions/CMO/solutions/sol_2015.pdf

We claim that the answer is $2n+2.$ Enumerate the horizontal gridlines and the vertical gridlines. For the vertical gridlines, let $r_i$ be the number of edges in the graph that cross the gridline, and define $c_i$ similarly. We see that column $i+1$ has exactly $\tfrac{r_i+r_{i+1}}{2}$ entrances, where we define $r_0=r_{4n+2}=0$ and similarly for rows. Then as each edge crosses exactly one gridline, we have $\sum_{i=0}^{4n+2}r_i+c_i=(4n+2)^2.$ If $\tfrac{r_i+r_{i+1}}{2}\leq 2n+1,\tfrac{c_i+c_{i+1}}{2}\leq 2n+1$ for each $i,$ summing over all $i$ shows that equality must hold everywhere. In particular $r_1=r_1+r_2=4n+2\implies r_2=0,$ absurd. Here is the construction for $n=6$; it is easy to see that it generalizes. [asy][asy] size(8cm); for (int i=0; i < 7; ++i) { draw((i,0)--(i,6),mediumgray); draw((0,i)--(6,i),mediumgray); } draw((0.5,5.5)--(5.5,5.5),red); draw((5.5,0.5)--(5.5,5.5),red); draw((5.5,0.5)--(4.5,0.5),red); draw((4.5,0.5)--(4.5,4.5),red); draw((2.5,4.5)--(4.5,4.5),red); draw((2.5,3.5)--(2.5,4.5),red); draw((3.5,3.5)--(2.5,3.5),red); draw((3.5,3.5)--(3.5,2.5),red); draw((3.5,2.5)--(2.5,2.5),red); draw((2.5,1.5)--(2.5,2.5),red); draw((2.5,1.5)--(3.5,1.5),red); draw((3.5,1.5)--(3.5,0.5),red); draw((3.5,0.5)--(0.5,0.5),red); draw((0.5,0.5)--(0.5,1.5),red); draw((0.5,1.5)--(1.5,1.5),red); draw((1.5,1.5)--(1.5,2.5),red); draw((1.5,2.5)--(0.5,2.5),red); draw((0.5,2.5)--(0.5,3.5),red); draw((0.5,3.5)--(1.5,3.5),red); draw((1.5,3.5)--(1.5,4.5),red); draw((1.5,4.5)--(0.5,4.5),red); draw((0.5,4.5)--(0.5,5.5),red); [/asy][/asy]

It makes $(4n+2)^2$ moves, where each one consists of entering one other row and one other column. Hence, across the entire journey, the turtle enters $8n+4$ rows and columns, not necessarily distinct. The expected number of times the turtle enters each row/column is $\tfrac{(4n+2)^2}{8n+4} = 2n+1$, with equality holding if and only if it enters each row and column the same number of times (more specifically, $2n+1$). This is not possible - consider, say the second column from the starting point. This column must be crossed an even number of times since the turtle is to return back to the first column. Hence, equality cannot hold and some row/column is crossed $\geq 2n+2$ times. There is probably a construction that crosses each row/column at most $2n+2$ times.

ABCDE and jj_ca888 your solutions are wrong (despite that you got the right answer) consider the following diagram for $n=1$ : [asy][asy] size(8cm); for (int i=0; i < 7; ++i) { draw((i,0)--(i,6),mediumgray); draw((0,i)--(6,i),mediumgray); } draw((0.5,0.5)--(0.5,1.5),red); draw((0.5,1.5)--(1.5,1.5),red); draw((1.5,1.5)--(1.5,2.5),red); draw((1.5,2.5)--(0.5,2.5),red); draw((0.5,2.5)--(0.5,5.5),red); draw((0.5,5.5)--(1.5,5.5),red); draw((1.5,5.5)--(1.5,3.5),red); draw((1.5,3.5)--(3.5,3.5),red); draw((3.5,3.5)--(3.5,4.5),red); draw((3.5,4.5)--(2.5,4.5),red); draw((2.5,4.5)--(2.5,5.5),red); draw((2.5,5.5)--(5.5,5.5),red); draw((5.5,5.5)--(5.5,4.5),red); draw((5.5,4.5)--(4.5,4.5),red); draw((4.5,4.5)--(4.5,3.5),red); draw((4.5,3.5)--(5.5,3.5),red); draw((5.5,3.5)--(5.5,0.5),red); draw((5.5,0.5)--(3.5,0.5),red); draw((3.5,0.5)--(3.5,1.5),red); draw((3.5,1.5)--(4.5,1.5),red); draw((4.5,1.5)--(4.5,2.5),red); draw((4.5,2.5)--(2.5,2.5),red); draw((2.5,2.5)--(2.5,0.5),red); draw((2.5,0.5)--(0.5,0.5),red); dot((0.5,0.5)); [/asy][/asy] where the turtle enters the second column three times .