## Maximum-bend TSP

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

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

## 1 Answer

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 2011 at 22:49
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 30, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9343315958976746, "perplexity_flag": "head"}