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?

-
Hi Michael, would you care spelling out the meaning of the acronym TSP? I don't know what it stands for. – André Henriques Aug 11 '11 at 20:39
I suspect he is using Traveling Salesman Path for Hamiltonian path. In many contexts, bends don't make much sense, but on the grid it becomes an interesting problem. I suspect some region argument (divide the grid into somewhat similar regions) might demonstrate the poster's conjecture. Gerhard "Ask Me Aboit System Design" Paseman, 2011.08.11 – Gerhard Paseman Aug 11 '11 at 21:12
It's a serious breach of etiquette to post this here just hours after posting it to math.stackexchange math.stackexchange.com/questions/56861/… especially without acknowledging that you are doing so. Voting to close. – Gerry Myerson Aug 11 '11 at 22:40

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...

-
By looking at corners, you can get $n^2 - 4$ as an upper bound for large n. I suspect the conjectured bound is tight. It might be provable by dividing the grid into diagonal regions, but I have not thought it through. Gerhard "Ask Me About System Design" Paseman, 2011.08.11 – Gerhard Paseman Aug 11 '11 at 22:49