Proposed by Oriol Solé Pi, Mexico. This was the coolest and the hardest problem on the exam.

By far the hardest and coolest problem on the exam. Here is a solution. Firstly, note that we can think of the problem not as moving a coin, but as drawing in diagonals and sides onto the board as to form a path of length $(n+1)^2 - 1 = n^2 + 2n$ on the vertices of the board. Also, we will orient on board so that its vertices are $(0, 0), (0, n), (n, 0),$ and $(n, n)$ on the Cartesian plane. We claim that the maximum number of diagonals we can draw is (quite surprisingly) $n^2$ if $n$ is even and $n^2 + n$ if $n$ is odd. First, let's provide the constructions. If $n$ is even, draw in all $n^2$ diagonals of the board which have slope $+1.$ Now, we essentially have $2n-1$ paths. Simply draw in $2n$ sides to merge these paths to finish (it's easy to see how to do this if you draw out the diagram). If $n$ is odd, then call one of the $n^2$ cells of the board tasty if its lower-left corner has even $y-$coordinate. Draw in all diagonals which are in tasty squares. Now, for $0 \le i \le n-1$, connect $(n, i)$ with $(n, i+1)$ if $i$ is even and $(0, i)$ with $(0, i+1)$ if $i$ is odd. Hence, we've shown that our claimed answers can indeed be obtained. Let's now show that they are optimal. We will consider two cases on $n$; the even case is substantially easier (but still not that easy). Case 1. $n$ is even. Set $n = 2k$ in this case. Color the vertices of the board in the standard way, i.e., let $(x, y)$ be black if $x+y$ is even and white if $x+y$ is odd, for vertices $(x, y)$ of the board. Call a black vertex $(x, y)$ wangy if $x$ is even and tangy if $x$ is odd. Notice that wangy vertices outnumber tangy vertices by exactly $2k+1.$ Let's now consider any possible path of Don Miguel's token. To it, we will associate a string of length $(n+1)^2$ of the characters $B$ and $W$, where we use a $B$ if the corresponding vertex is black and a $W$ if it's white. For instance, the path $(0, 0) \rightarrow (0, 1) \rightarrow (1, 0) \rightarrow (2, 0) \rightarrow (1, 1) \rightarrow (0, 2) \rightarrow (1, 2) \rightarrow (2, 1) \rightarrow (2, 2)$ is associated to the string $BWWBBBWWB.$ Notice that the number of sides in Don Miguel's path (i.e. a move in one of the four cardinal directions) is precisely equal to the number of "color changes" in our string. Call a $B-$block any group of vertices which correspond to a contiguous block of $B$'s in the string. Observe that each $B-$block can have at most one more wangy than tangy vertices. This is clear since wangy and tangy vertices alternate in any $B-$block. Hence, since wangy vertices outnumber tangy vertices by $2k+1$, we know that there are at least $2k+1$ $B-$blocks, which imply that there are at least $2 \cdot (2k+1 - 1) = 4k$ color changes in our string. This corresponds to at least $4k$ sides in Don Miguel's path, giving at most $n^2 + 2n - 4k = n^2$ diagonals, as desired. Case 2. $n$ is odd. First, see https://artofproblemsolving.com/community/c5h202936p1116367 (post #19) for some inspiration. After familiarizing ourselves with the solution to the above hard problem, we are ready to tackle the odd case. Again, color a vertex $(x, y)$ of the board black if $x+y$ is even and white if $x+y$ is odd. Consider any possible path that Don Miguel's token may take. Again, associate to it a string of length $(n+1)^2,$ and define $B-$blocks similarly. Additionally, define $W-$blocks analogously. Let's now observe the set of white vertices of the board. After an appropriate transformation, it is in fact equivalent to the set of lattice points in the problem linked above! We therefore know that there must be at least $\frac{n+1}{2}$ $W-$blocks in the string, because a $W-$block in the string can be seen to be equivalent to a path in the linked problem. Analogously, there must be at least $\frac{n+1}{2}$ $B-$blocks, and these imply that there must be at least $2 \cdot \frac{n+1}{2} - 1 = n$ color changes. This implies that there are at least $n$ sides in Don Miguel's path, hence implying that there are at most $n^2 + 2n - n = n^2 +n$ diagonals, as desired. As we've exhausted all cases, we've shown that the answer is $n^2$ if $n$ is even and $n^2+n$ if $n$ is odd. $\square$

Solution from Twitch Solves ISL: When $n$ is odd, the answer is $n^2+n$, while when $n$ is even, the answer is $n^2$. Constructions are shown below for $n=9$ and $n=8$ which obviously generalize. [asy][asy] size(12cm); path green_zigzag = (0,1)--(1,0)--(2,1)--(3,0)--(4,1)--(5,0)--(6,1)--(7,0)--(8,1)--(9,0); path blue_zigzag = (0,0)--(1,1)--(2,0)--(3,1)--(4,0)--(5,1)--(6,0)--(7,1)--(8,0)--(9,1); for (int t=0; t<=9; ++t) { draw((0,t)--(9,t), lightgrey); draw((t,0)--(t,9), lightgrey); } draw(box( (0,0),(9,9)), grey ); for (int i=0; i<5; ++i) { draw(shift(0,2*i)*green_zigzag, deepgreen); draw(shift(0,2*i)*blue_zigzag, blue); draw( (9,2*i)--(9,2*i+1), red+1.5 ); if (i != 4) { draw( (0,2*i+1)--(0,2*i+2), red+1.5 ); } } for (int x=0; x<=9; ++x) { for (int y=0; y<=9; ++y) { if ((x+y)#2 == (x+y)/2) { dot( (x,y), blue ); } } } for (int t=0; t<=8; ++t) { draw((10,t)--(18,t), lightgrey); draw((t+10,0)--(t+10,8), lightgrey); } draw(box( (10,0),(18,8)), grey); for (int i=0; i<=4; ++i) { draw((10+2*i,0)--(10,2*i), blue); draw((10+2*i,8)--(18,2*i), blue); } for (int i=0; i<4; ++i) { draw((10+2*i+1,0)--(10,2*i+1), deepgreen); draw((10+2*i+1,8)--(18,2*i+1), deepgreen); draw((2*i+10,0)--(2*i+10+1,0), red+1.5); draw((2*i+10+1,8)--(2*i+10+2,8), red+1.5); draw((10,2*i+1)--(10,2*i+2), red+1.5); draw((18,2*i)--(18,2*i+1), red+1.5); } for (int x=0; x<=8; ++x) { for (int y=0; y<=8; ++y) { if ((x+y)#2 == (x+y)/2) { dot( (x+10,y), blue); } } } label("$n=9$", (4.5,0), dir(-90)); label("$n=8$", (14,0), dir(-90)); [/asy][/asy] To show the bound, impose coordinates $(x,y)$ with $0 \le x \le n$ and $0 \le y \le n$, and color blue any point with $x+y \equiv 0 \pmod 2$ (as shown in the examples above); else color it green (not drawn). Imagine taking our given path and deleting every orthogonal move of distance $1$ (i.e.\ not $\sqrt2$). Doing this deletion gives us a bunch of zigzags --- graph-theoretic paths of length $1$ or more where every two adjacent vertices are $\sqrt 2$ apart. The zigzags will alternate between passing through blue dots (we call these blue zigzags) and through green dots (we call these green zigzags). Case where $n$ is even We give an estimate on the number of blue zigzags. Claim: If $n$ is even, there are at least $n+1$ blue zigzags. Proof. There are $\left( \frac{1}{2} n + 1 \right)^2$ blue dots in odd-numbered rows, and $\left( \frac{1}{2} n \right)^2$ blue dots in even-numbered rows. The difference between this is $n+1$. Since blue zigzags must alternate between odd-numbered rows and even-numbered rows, there must be at least $n+1$. $\blacksquare$ Since we know there are at least $n+1$ blue zigzags, there must have been at least $n$ green zigzags, so there were a total of at least $2n+1$ zigzags. In other words, there were at least $2n$ orthogonal moves in the original given path. So the number of diagonal steps is at most $((n+1)^2-1)-2n = n^2$. Case where $n$ is odd The blue and green zigzags play the same role, so we bound both: Claim: [USAMO 2008/3] If $n$ is odd, there are at least $\frac{n+1}{2}$ blue zigzags, and at least $\frac{n+1}{2}$ green zigzags. Proof. This is USAMO 2008 problem 3 rotated by $90^{\circ}$. $\blacksquare$ Hence there were a total of at least $n+1$ zigzags. In other words, there were at least $n$ orthogonal moves in the original given path. So the number of diagonal steps is at most $((n+1)^2-1)-(n+1) = n^2+n$.

Here's an alternative, simpler? proof of the bound. This might also end up being a proof for USAMO 2008/3 again but I haven't checked. Call a diagonal red or blue based off $x + y \pmod{2}$. Ignore horizontal/vertical edges and only considers diagonal ones. Note that diagonals connect lattice points with the same parity of $x + y$. It then remains to consider red and blue diagonals separately. Claim: An $n \times n$ grid has at most $\frac{n^2}{2}$ red diagonals if $2 \mid n$ and else it has at most $\frac{n(n+1)}{2}$ such diagonals. Take a covering collection of paths. If $n$ is even, we can force the following red diagonals by placing the diagonals at the red dots and removing another diagonal if necessary (which is at most $1$ by the guarentee of being a collection of paths). This then forces the purple squares to be empty, and then induct down on a $(n-2) \times n$ grid. [asy][asy] size(5cm); int W=4; int H=4; for (int i=0; i<=W; ++i) { draw( (i,0)--(i,H), rgb("333333")+dotted ); } for (int i=0; i<=H; ++i) { draw( (0,i)--(W,i), rgb("333333")+dotted ); } dot((0,4), red); dot((2,4), red); dot((4,4), red); draw((0,4)--(1,3)--(2,4)--(3,3)--(4,4), red); pen pl = purple+white; fill((0,2)--(0,3)--(4,3)--(4,2)--cycle, pl); [/asy][/asy] If $n$ is odd, the same idea also applies with inducting down on a $n-2 \times n-2$ grid. [asy][asy] size(5cm); int W=5; int H=5; for (int i=0; i<=W; ++i) { draw( (i,0)--(i,H), rgb("333333")+dotted ); } for (int i=0; i<=H; ++i) { draw( (0,i)--(W,i), rgb("333333")+dotted ); } dot((0,5), red); dot((2,5), red); dot((4,5), red); dot((5,0), red); dot((5,2), red); dot((5,4), red); draw((0,5)--(1,4)--(2,5)--(3,4)--(4,5)--(5,4)--(4,3)--(5,2)--(4,1)--(5,0), red); pen pl = purple+white; fill((0,3)--(0,4)--(4,4)--(4,0)--(3,0)--(3,3)--cycle, pl); [/asy][/asy]