MHB Given $n$ points in the plane, any listing (permutation) $p_1, p_2,\dots,p_n$

[Ackbach]

Here is this week's POTW:

-----

Given $n$ points in the plane, any listing (permutation) $p_1, p_2,\dots,p_n$ of them determines the path, along straight segments, from $p_1$ to $p_2$, then from $p_2$ to $p_3,\dots,$ ending with the segment from $p_{n-1}$ to $p_n$. Show that the shortest such broken-line path does not cross itself.

-----

Remember to read the https://mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to https://mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Congratulations to castor28 for his correct solution to this week's POTW, which was Problem 89 in the MAA Challenges. His solution follows:

[sp]We will prove the contrapositive: if a path crosses itself, there exists a shorter path. Assume that we have a path $\ldots AB\ldots CD\ldots$, where the segments $AB$ and $CD$ intersect at the point $O$. Since each point is visited only once, $O$ is not one of the given points. This path is shown in black in the figure below:

\begin{tikzpicture}[>=stealth]
\path (-6,0) (0,0) coordinate (O) node

{$O$}
(-2,-4) coordinate (A) node

{$A$}
(1,2) coordinate (B) node

{$B$}
(-1,1) coordinate (C) node

{$C$}
(2,-2) coordinate (D) node [below] {$D$};
\draw[->] (A) -- (B);
\draw[->] (C) -- (D);
\draw[dotted, ->,bend right=30] (B) to (C);
\draw[red,->, dashed] (A) -- (C);
\draw[red,->, dashed] (B) -- (D);
\draw[dotted,<-] (A) -- ++(-1,0);
\draw[dotted,->] (D) -- ++(1,0);
\end{tikzpicture}

where the sections before $A$, between $B$ and $C$, and after $D$ have been shown as dotted lines.

The triangles $AOC$ and $BOD$ show that we have:
$$\begin{align*}
AC &< AO + OC\\
BD &< BO + OD
\end{align*}$$
and therefore $AC+BD < AB + CD$.

This means that if we replace the segments $AB$ and $CD$ with the segments $AC$ and $BD$ (shown in red), and reverse the direction of the section between $B$ and $C$, we get a shorter path $\ldots AC\ldots BD\ldots$; this shows that the initial path is not the shortest possible.[/sp]​