Welcome to our community

Be a part of something great, join today!

Problem Of The Week # 309 - May 08, 2018

Status
Not open for further replies.
  • Thread starter
  • Admin
  • #1

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,198
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 POTW submission guidelines to find out how to submit your answers!
 
  • Thread starter
  • Admin
  • #2

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,198
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.