Return to Answer

4 deleted 12 characters in body

Let me write $f(n) = n^{2}-n$ for even $n$ and $f(n) = n^{2}-n-1$ for odd $n$.

I can show that

It's certainly the maximum number of turns is case that you can do at least as well as $f(n)$. More precisely, I can show that there is a path with $f(n)$ turns that ends up at the top right corner of the grid, and which arrived there from the point below that.

It's easy to check this for $n=2$ or $n=3$, and we can handle the rest by induction (the inductive step being the reason it's important to generate examples that end up at the top right corner).

Suppose we have a path that works for an $(n-2) \times (n-2)$ grid; I'll call it the $(n-2)$-path. We proceed by extending this $(n-2)$-path to an $n$-path.

Place the $(n-2)$-path at the top left corner of the $n \times n$ grid, leaving two columns to the right and two rows below the path. Start from the end point at the top right corner of the $(n-2)$-path. Extend the path two grid points rightwards, to the edge of the grid.

Now we split into two cases. If $n$ is even, snake down the right side of the grid, then across the bottom of the grid, finishing, via a down-move, at the bottom left corner. This procedure adds $4n-6$ bends to the original path, and so has $(n-2)^2 - (n-2) + 4n-6 = n^{2}-n$ bends. Finally, rotate the resulting path to give you a path with $n^{2}-n$ bends that ends with an up-move at the top right corner.

If $n$ is odd, then snake down the right side of grid. There is one small modification due to the oddness: you have to stop snaking just before you hit the bottom right. (At this point I wish I knew how to draw a nice picture.) Then resume snaking along the bottom of the grid. As before, you finish at the bottom left corner, via a down-move. Again, this adds $4n-6$ bends to the original path, so has $(n-2)^{2}-(n-2)-1 + 4n-6 = n^{2}-n-1$ bends. Finally, rotate the path to give an $n$-path that ends up at the top right.

There must be some neat argument to show that you can't do better than $f(n)$, but I can't see it yet...

3 added 110 characters in body

Let me write $f(n) = n^{2}-n$ for even $n$ and $f(n) = n^{2}-n-1$ for odd $n$.

I can show that the maximum number of turns is at least $f(n)$. More precisely, I can show that there is a path with $f(n)$ turns that ends up at the top right corner of the grid, and which arrived there from the point below that.

It's easy to check this for $n=2$ or $n=3$, and we can handle the rest by induction (the inductive step being the reason it's important to generate examples that end up at the top right corner).

Suppose we have a path that works for an $(n-2) \times (n-2)$ grid; I'll call it the $(n-2)$-path. We proceed by extending this $(n-2)$-path to an $n$-path.

Place the $(n-2)$-path at the top left corner of the $n \times n$ grid, leaving two columns to the right and two rows below the path. Start from the end point at the top right corner of the $(n-2)$-path. Extend the path two grid points rightwards, to the edge of the grid.

Now we split into two cases. If $n$ is even, snake down the right side of the grid, then across the bottom of the grid, finishing, via a down-move, at the bottom left corner. This procedure adds $4n-6$ bends to the original path, and so has $(n-2)^2 - (n-2) + 4n-6 = n^{2}-n$ bends. Finally, rotate the resulting path to give you a path with $n^{2}-n$ bends that ends with an up-move at the top right corner.

If $n$ is odd, then snake down the right side of grid. There is one small modification due to the oddness: you have to stop snaking just before you hit the bottom right. (At this point I wish I knew how to draw a nice picture.) Then resume snaking along the bottom of the grid. As before, you finish at the bottom left corner, via a down-move. Again, this adds $4n-6$ bends to the original path, so has $(n-2)^{2}-(n-2)-1 + 4n-6 = n^{2}-n-1$ bends. Finally, rotate the path to give an $n$-path that ends up at the top right.

There must be some neat argument to show that you can't do better than $f(n)$, but I can't see it yet...

2 added 9 characters in body

Let me write $f(n) = n^{2}-n$ for even $n$ and $f(n) = n^{2}-n-1$ for odd $n$.

I can show that the maximum number of turns is at least $f(n)$. More precisely, I can show that there is a path with $f(n)$ turns that ends up at the top right corner of the grid, and which arrived there from the point below that.

It's easy to check this for $n=2$ or $n=3$, and we can handle the rest by induction.

Suppose we have a path that works for an $(n-2) \times (n-2)$ grid; I'll call it the $(n-2)$-path. We proceed by extending this $(n-2)$-path to an $n$-path.

Place the $(n-2)$-path at the top left corner of the $n \times n$ grid, leaving two columns to the right and two rows below the path. Start from the end point at the top right corner of the $(n-2)$-path. Extend the path two grid points rightwards, to the edge of the grid.

Now we split into two cases. If $n$ is even, snake down the right side of the grid, then across the bottom of the grid, finishing, via a down-move, at the bottom left corner. This procedure adds $4n-6$ bends to the original path, and so has $(n-2)^2 - (n-2) + 4n-6 = n^{2}-n$ bends. Finally, rotate the resulting path to give you a path with $n^{2}-n$ bends that ends with an up-move at the top right corner.

If $n$ is odd, then snake down the right side of grid. There is one small modification due to the oddness: you have to stop snaking just before you hit the bottom right. (At this point I wish I knew how to draw a nice picture.) Then resume snaking along the bottom of the grid. As before, you finish at the bottom left corner, via a down movedown-move. Again, this adds $4n-6$ bends to the original path, so has $(n-2)^{2}-(n-2)-1 + 4n-6 = n^{2}-n-1$ bends. Finally, rotate the path to give an $n$ path n$-path that ends up at the top right. There must be some neat argument to show that you can't do better than$f(n)\$, but I can't see it yet...

1