Between six towns

[BMAD]

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.

[bushindo]

Therefore

We can 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 triangle ABC, let angleC > 120° > angle B > angle A. Let the side opposite angle A have length a, and so on.

Then, by the cosine rule c² = a² + b² − 2ab cos C > a² + b² + ab. (Since cos C < −½.)

Assuming a < b (by 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.

I believe there is a subtle error here

See the part highlighted in red. Let's work backward and see what kind of condition we need to guarantee strict equality.

From c² = a² + b² − 2ab cos C, we see that if C = 120 and a = b, then c/a = sqrt(3), so far so good.

Now, let's examine the following critical part

"since M > c and m < a, we conclude that M/m > "

If c/a = sqrt(3), then to guarantee M/m = sqrt(3), we need to show that M = c AND m = a. That part wasn't proved anywhere. In fact, I believe that if we go back and look at the problem, then we would see that if we have a sub-triangle with side-ratio c/a = sqrt(3), then either M > c or m < a.

[dark_magician_92]

Can the arrangment be 3-D? i guess not.

[bonanova]

Let 5 towns be arranged 1 mile from a central town at equal angles.
They form a regular pentagon.
The distance between closest neighbors on the perimeter is 2 sin (36^o) = 1.1755...miles.

So no two towns are closer than 1 mile.

The distance between all other perimeter town pairs is the edge length times the golden ratio PHI = 1.618

So M = 1.902 = sqrt(3.62).

There must be a more compact arrangement of six towns.

A hexagon is worse, with M = 2 = sqrt(4).

[bonanova]

I would be interested to see the configuration that makes M = m * sqrt(3)

Clustering 6 dots as tightly as possible suggests using 1 central dot and 5 peripheral dots.

1. We construct black circles of radius 0.5 and prohibit overlap to set minimum unit pairwise distance.
2. We construct red circles of radius sqrt (3) and require each circle to contain the other five dots to set the maximum pairwise distance.

Spreading the points as much as (2) permits results in overlap of the central circle with all peripheral circles, violating (1).

Only the relevant arcs of the peripheral circles are shown, for clarity.

The figure demonstrates that M > m * sqrt (3), but leaves one wondering how equality could be achieved.

Previous post showed that M = m * 1.9 is achievable.

[BMAD]

Show that, unless the towns are all collinear, it is always possible to choose three of them so that they form a triangle with maximum angle of at least 120°.

[BMAD]

I marked it solved originally but just realized you didn't show equality yet. Sorry.

I would be interested to see the configuration that makes M = m * sqrt(3)

Clustering 6 dots as tightly as possible suggests using 1 central dot and 5 peripheral dots.

1. We construct black circles of radius 0.5 and prohibit overlap to set minimum unit pairwise distance.
2. 
   
3. We construct red circles of radius sqrt (3) and require each circle to contain the other five dots to set the maximum pairwise distance.
4. 
   

Spreading the points as much as (2) permits results in overlap of the central circle with all peripheral circles, violating (1).

six cities.gif

Only the relevant arcs of the peripheral circles are shown, for clarity.

The figure demonstrates that M > m * sqrt (3), but leaves one wondering how equality could be achieved.

Previous post showed that M = m * 1.9 is achievable.

[k-man]

I think you should mark this as solved. There is no way to place 6 points on a surface in a way that the minimum distance between any 2 points was m and the maximum distance between any 2 points was m*sqrt(3).

Let's start with one town and identify the area where the rest of the towns should be. This area is marked in red

Now, since we must have another town at the distance of m from the first, let's put it there and show the remaining area for the rest of the towns.

There are 2 red areas that should contain the remaining 4 towns. The distance between these two areas is exactly m*sqrt(3), which means that the only combinations that allow both areas to be used are marked as pairs of blue, green and purple dots. Choosing any pair of these dots eliminates any other possible locations for more towns. This way we get only 4 towns.

However, there is no way to fit 4 more towns in only one of these red areas. Below pictures aren't a formal proof, but make it pretty obvious that no more than 5 towns can be placed under these constraints. Black dots are committed towns. Red areas are remaining valid areas. Blue, green and purple dots are mutually exclusive with each other and red areas.

[bonanova]

I am exploring one more possibility.

I enforced minimum separation by drawing equal sized circles (radius m/2) around every point. That is sufficient, but not necessary. The five peripheral points could have larger radii at the expense of the central point. Putting another way, my five circumferential circles were not tightly packed - there was space between them.

The problem reduces to finding the radius of the largest circle that can fit within the largest non overlapping circles centered on the vertices of a regular pentagon. That is what I am working on now.

Again referring to my previous post, this would re-scale the red circles, and they might then include the other five points.

[k-man]

I am exploring one more possibility.

I enforced minimum separation by drawing equal sized circles (radius m/2) around every point. That is sufficient, but not necessary. The five peripheral points could have larger radii at the expense of the central point. Putting another way, my five circumferential circles were not tightly packed - there was space between them.

The problem reduces to finding the radius of the largest circle that can fit within the largest non overlapping circles centered on the vertices of a regular pentagon. That is what I am working on now.

Again referring to my previous post, this would re-scale the red circles, and they might then include the other five points.

equal to the circumradius of the pentagon minus m/2. Circumradius of the regular pentagon is m*sqrt((5+sqrt(5)/10) or approx. 0.850651m. So the radius you're looking for is approx. 0.350651m.

So, assuming that this is the most compact way to pack 6 points on the surface, so that m is the shortest distance between any of them, then m*sqrt((5+sqrt(5)/10) or approx 0.850651m is the minimum longest distance.

[bonanova]

I won't spoiler this because it's not a solution but a refutation.

Consider a regular pentagon with side t and points at center and vertices.

The radius r of the circumcircle is the minimum distance among the six points.

The diagonal d is the maximum distance among the six points.

t = 2r sin 36^o = 1.1756 r

d = PHI t where PHI is the golden ratio = 1.618...

M/n = d/r = 2 PHI sin 36^o = 1.902 = sqrt (3.618) > sqrt (3).

This is the answer from my where I conjectured a more dense arrangement of points.

I don't believe there is a more dense configuration of six points.

[BMAD]

There is a proof that i have that show's that it should be possible but what you present is something that i reference in my proof as well.

[bonanova]

A proof would be interesting to see.

A post on red hot pawn, where this problem was discussed a few years back, makes this claim:

See: http://www.redhotpawn.com/board/showthread.php?threadid=141670&page=&page=3

I agree with this reasoning for some sufficiently large number of points in the plane. However, I am not sure how this translates to, say, the initial problem of 6 points in the plane. I do not really know the answer yet. The best I have come up with is the same as what Palynka [the pentagon 1.902 answer] proposed, but I do not have a proof that it is the minimum. I do have a proof that, for example, the answer cannot be less than y/x = sqrt(3). But that does not help that much.

He does not post the proof itself, although I believe it.

But note his proof is "cannot be less than" which is different from "can be equal to."

[BMAD]

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 know 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 can deduce that M/m ...

**i am breaking the proof up because the site won't let me post it all at once**

[BMAD]

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°

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

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.

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

[BMAD]

Therefore

We can 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 triangle ABC, let angleC > 120° > angle B > angle A. Let the side opposite angle A have length a, and so on.

Then, by the cosine rule c² = a² + b² − 2ab cos C > a² + b² + ab. (Since cos C < −½.)
Assuming a < b (by 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.

[BMAD]

**now as noted by Bonanova, and even though i have proved M/m , I have been unable to create a 'real example' of where this can occur. The smallest configuration that i have been able to see myself, as of yet, is 2 sin 72° = 1.902 which is close but still no cigar.

Edited April 11, 2013 by BMAD

[bonanova]

It shows that

(a) sqrt(3) is violated if three points form an angle greater than 120 degrees and

(b) that in no case can a 120 degree (or greater) be avoided.

I have the notion, and will see if it's true, that, for triangle and quadrilateral hull cases, one interior point can avoid violation of 120, but only one.

Because, for pentagon and hexagon hulls, some group of three of the perimeter points must exceed 120, that would then prove the strict inequality. Indeed, the 1.902 value derives from three perimeter points violating 120 for the pentagon.

[bonanova]

Hexagon:

Regular is best case: Interior angles are 120. But diameter = 2.
Otherwise, at least one interior angle > 120.

Pentagon:

Regular is best case: Diameter = 1.902
Otherwise, at least one diameter > 1.902.

Quadrilateral:

Best try is the 60 - 120 - 60 - 120 Rhombus. (Two concatenated regular triangles.)
Here, each regular triangle can have an iterior point that shares its 360 degrees equally among the vertices.
But that makes four of the points collinear. Diameter = 3.
With any quadrilateral, the two interior points have the impossible task of splitting their 360 among the vertices of their parent triangle PLUS an edge drawn to the other interior point, thus adding a fraction of one of those 120 angles to one of the other 120 angles.

Triangle:

Largest angle = 120. No interior point can share its 360 degrees equally among the vertices.
Largest angle < 120: One interior point can share its 360 degrees equally among the vertices.
But only one. The other two interior points will violate 120.

I think this shows that the 120 constraint is violated for every hull.
sqrt (3) is not achievable, it is just the greatest easily proved lower bound.

I'm convinced that the greatest lower bound is 1.902

[BMAD]

I came across this page which seems to contradict my proof. Any ideas where I went wrong?

http://www2.stetson.edu/~efriedma/maxmin/

[bonanova]

I came across this page which seems to contradict my proof. Any ideas where I went wrong?

http://www2.stetson.edu/~efriedma/maxmin/

Your proof did not go "wrong": 1.902 IS "greater than or equal to" sqrt(3).

What others have said is that 1.902 cannot be "equal to" sqrt(3).

As several people now have shown, the best lower bound for M/m is 1.902, where equality can be achieved.