Welcome to MathOverflow

Question

2

1

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?

flag	asked Aug 11 2011 at 15:57 Michael 21●1

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 2011 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 2011 at 21:12

1

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 2011 at 22:40

Ian Martin · Answer 1 · 2011-08-13 07:55:55Z UTC

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

Maximum-bend TSP

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.