Solution to puzzle 140: Six towns

The smallest distance between any two of six towns is m miles. The largest distance between any two of the towns is M miles. Show that M/m . Assume the land is flat.

We idealize the towns as points. If any three of the points are collinear, so that C lies on AB, and (without loss of generality) AC CB, then AB/AC 2. Since M AB and m AC, we must have M/m 2 > , and so the condition holds. Hence in the remainder of the proof we may assume that no three points are collinear.

We now show that it is always possible to choose three of the six points so that they form a triangle with maximum angle of at least 120°. From this we deduce that M/m .

Consider the convex hull of the points. This may be a triangle, quadrilateral, pentagon, or hexagon. We consider each case in turn.

Triangle

If the convex hull consists of a triangle ABC, then consider one of the three interior points D. In one of the triangles ABD, BCD, or ADC, the angle at D must be greater than or equal to 120°.

Sample convex hull ABC, with internal point D.

Quadrilateral

If the convex hull is a quadrilateral ABCD, then one of the two interior points E lies inside triangle ABC or ACD, and hence reduces to the triangular case, above. That is, assuming (without loss of generality) that E lies inside ABC, then in one of the triangles ABE, BCE, or AEC, the angle at E must be greater than or equal to 120°.

Sample convex hull ABCD, with internal point E, within triangle ABC.

Pentagon

If the convex hull is a pentagon ABCDE, then the interior point F lies inside one of the triangles ABC, ACD, or ADE, formed by drawing diagonals AC and AD, and hence reduces to the triangular case, above.

Sample convex hull ABCDE, with internal point F, within triangle ABC.

Hexagon

If the convex hull is a hexagon ABCDEF, then one of the internal angles must be greater than or equal to 120°. Join the two adjacent vertices to form a triangle with an internal angle greater than or equal to 120°.

Sample convex hull ABCDE, with internal point F.

Conclusion

We now show that, in a triangle with internal angle at least 120°, the ratio of the length of the longest side to the shortest side is at least : 1.

Without loss of generality, in ABC, let C 120° > B A. Let the side opposite A have length a, and so on.

Triangle ABC, with angles as described as above.

Then, by the law of cosines (also known as the cosine rule),
c² = a² + b² − 2ab cos C a² + b² + ab. (Since cos C −½.)
Assuming a b (which is indeed the case by the law of sines (also known as the sine rule)), we obtain c² 3a².
Hence c/a .

Finally, since M c and m a, we conclude that M/m , as was to be proved.

Remarks

Although we have shown that M/m , it is not clear that equality can occur. Is there a configuration of six points such that M/m = ? If not, what is the smallest possible value of M/m? The smallest value I'm aware of is 2 sin 72° = 1.902, which is achieved with a regular pentagon and its center. However, I don't have a proof that this is the minimum possible value.

What is the smallest possible value of M/m for seven points in the plane?

Source: To be announced