Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose $A_1,A_2,A_3,\ldots,A_n$ are distinct points in the plane. A closed path on those points is formed from a permutation of the points, with line segments drawn between successive points (and with a segment connecting the last point to the first, to make the path “closed”). For the six points pictured below on the left, the next three pictures indicate paths corresponding to the permutations $A_1A_2A_3A_4A_5A_6$, $A_1A_3A_6A_2A_4A_5$, and $A_1A_3A_6A_2A_5A_4$.

enter image description here

Prove: No matter how $n$ distinct points $A_1,A_2,A_3,\ldots,A_n$ are placed in the plane, the shortest closed path on those points has no crossings.

share|improve this question
2  
Use triangle inequality theorem. –  hjpotter92 Mar 6 '13 at 9:15
    
Triangle inequality and induction on the number of crossings in your shape. –  dtldarek Mar 6 '13 at 9:19
add comment

2 Answers 2

If $a, \ldots, b, c, \ldots, d, e, \ldots a$ is a closed path with $bc$ and $de$ intersecting, show that $a, \ldots b, d, \ldots c, e, \ldots a$ is shorter.

share|improve this answer
add comment

Given $n$ points in the plane, there are a finite number of ways of connecting them in to a loop. Note that each loop has a finite total length. Suppose we begin with a loop $X$ which has a crossing. Let a crossing of $X$ be the line segments $[a,b]$ and $[c,d]$. We can replace the loop $X$ by two other graphs $X'$ and $X''$ given by removing the line segments above and replacing them with $[a,c]$ and $[b,d]$ for $X'$ and with $[a,d]$ and $[b,c]$ for $X''$. Precisely one of $X'$ and $X''$ will be a loop.

WLOG suppose it is $X'$ which is a loop. It should be clear (but you can prove this using the triangle inequality) that by 'uncrossing' two crossed segments as was done above, the total length of the loop has been decreased. There are now two possible cases for the state of $X'$. Either $X'$ now has no crossings, in which case we are done as we have shown that $X$, with crossings, did not have minimal length, or $X'$ still has crossings (possibly new ones added in by the uncrossing). In the second case, simply repeat the above to get a new loop with shorter total length. After each repetition, the total length is reduced, and there are only a finite number of total lengths that a loop can have. It follows that we will eventually reach a loop with 0 crossings which has total length less than the original loop with a crossing.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.