most recent 30 from http://mathoverflow.net 2013-05-24T19:26:09Z http://mathoverflow.net/feeds/question/72699 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/72699/maximum-bend-tsp Michael 2011-08-11T15:57:33Z 2011-08-13T07:55:55Z

<p>I've seen minimum-bend TSP studied, has anyone looked at max-bend TSP?</p> <p>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.</p> <p>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?</p>

http://mathoverflow.net/questions/72699/maximum-bend-tsp/72724#72724 Ian Martin 2011-08-11T22:31:18Z 2011-08-13T07:55:55Z

<p>Let me write $f(n) = n^{2}-n$ for even $n$ and $f(n) = n^{2}-n-1$ for odd $n$.</p> <p>It's certainly the case that you can do at least as well as $f(n)$. More precisely, <em>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</em>.</p> <p>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).</p> <p>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.</p> <p>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.</p> <p>Now we split into two cases. If <strong>$n$ is even</strong>, 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.</p> <p>If <strong>$n$ is odd</strong>, 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.</p> <p>There must be some neat argument to show that you can't do better than $f(n)$, but I can't see it yet...</p>