Maximum-bend TSP I've seen minimum-bend TSP studied, has anyone looked at max-bend TSP?
As a special case, I'm interested in the maximum number of turns a hamiltonian path can take in an $n \times n$ square grid.
I think it should be $n^2 - n$ for even $n$ and $n^2 - n - 1$ for odd $n$, but does anyone know a proof?
 A: Let me write $f(n) = n^{2}-n$ for even $n$ and $f(n) = n^{2}-n-1$ for odd $n$.
It's certainly the case that you can do at least as well as $f(n)$.  More precisely, 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...
