# Problem Of The Week # 309 - May 08, 2018

Status
Not open for further replies.

#### Ackbach

##### Indicium Physicus
Staff member
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.

-----

#### Ackbach

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

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

Status
Not open for further replies.