[Puzzleblogger Kevan Choset, September 26, 2005 at 2:43pm] Trackbacks

Imagine you have an equilateral triangle 2 inches to a side. Prove that no matter how you draw 5 points within the triangle (anywhere in the interior or on the perimeter), there will be two points an inch or less away from each other.

Daniel Chapman (mail):
I get it... the REAL puzzle is figuring out how to explain something in text that is so easily explained with a pen, paper, and common sense.
9.26.2005 3:49pm
Syd Henderson (mail):
Connect the midpoints of the sides of the triangle; this divides the triangle into four smaller equilateral triangles whose sides are each one inch long. At least two of the five points must be contained within or on the perimeter of one of the four small triangle, hence are less than one inch apart.
9.26.2005 3:56pm
alkali (mail) (www):
Divide the triangle into 4 equilateral triangles of side 1". (How to do this, if it's not clear: stack /\ on top of /\/\.)

If you choose any 5 points in the triangle, at least two of the points must be in the same 1" equilateral triangle, and therefore 1" or less away from each other.

Some of these bits could use more rigorous argument, I suppose.
9.26.2005 4:01pm
William Spieler (mail) (www):
Take the three points furthest from each other, i.e., the three vertices. Then take the point furthest from each point, i.e, the midpoint of the triangle. That point is 2/√(3) (≈1.55) from each vertex. Any other point will be at least 1/√3 (≈0.577) from some other point.
9.26.2005 4:05pm
If three of the points are on the apicies, that would set them 2 inches apart from each other. If the fourth was placed at the center it would be 1.155 inches from the other three. (Bisect into right triangle, height equals square root of 3, use similar triangles rule to get distance from apex to center of 2/(sqrt 3) = 1.155. There is no place to put a fifth point which is more than an inch away from all of the others.
9.26.2005 4:05pm
William Spieler (mail) (www):
The bisection of one of the sides is √3, by the way. The distance from the midpoint of a side to the center is 1/√3.
9.26.2005 4:06pm
Area of rectaingle defined by the triangle = sqrt(3) * 2. Assume a placement of the points were possible. Area of 1 inch circle = Pi. The area occupied by the 1 inch circles surrounding each point would be at least 5*Pi/4 as each circle would have to be at least 1/4 contained in the rectangle. 5*Pi/4 is greater than the sqrt(3)*2, the area of the rectangle. So placing the points isn't possible in the rectangle. If it isn't possible in the rectangle, it isn't possible in the triangle which is contained within the rectangle.
9.26.2005 4:07pm
William Spieler (mail) (www):
Brogie's calculation of 2/√3 is correct; I left out the tenth decimal.
9.26.2005 4:07pm
GMUSL 1L (mail):
I think that the above commenters are correct in that they're subdividing the triangle, but I would do it differently.

I'd use a compass to draw a 1" radius line from each point of the equilateral within the triangle. That would leave a "concave triangle" of an infinite # of points more than an inch away from all of the end points.

Once you have this "concave triangle" of points, then you can draw the interior equilateral that the previous ocmmenters mentioned (which completely surrounds the smaller "concave triangle", though it shares all 3 points). Because all points within the smaller equilateral triangle are within 1" of each other, all points within or on the "concave triangle" must be within 1" of each other. Thus, having 2 points all more than 1" away from any other point on the triangle.

Using a compass to determine the points' radii (rather than just subdividing into smaller equilateral triangles) will show visually that there is no arrangement in which 5 circles of 1" radius that can fit at least their center points into an equilateral triangle of 2" on a side.
9.26.2005 4:11pm
John Armstrong (mail):
Brogie's method, unfortunately, only proves that a greedy algorithm can't get a valid configuration. Syd Henderson's method gets it the most elegantly.

Incidentally, is there any importance to the fact that so many of the puzzles recently have basically hinged on the Dirichlet drawer principle?
9.26.2005 4:12pm
GMUSL 1L (mail):
Also, if the problem allowed points to be EXACTLY 1" apart (rather than infinitessimally more), the equilateral triangle would fit exactly 6 points.
9.26.2005 4:17pm
statfan (mail):
informer, your proof ignores the case where some of the circle is outside of the triangle -- that is, when the point is near the edge of the triangle.
9.26.2005 4:23pm
Gordon (mail):
Geometry was my least favorite subject in Math.

And this is a good example of why!
9.26.2005 4:24pm
lncInPark (mail):
Restate the problem as follows: image that you have 5 circles of radius 1 inch where each circle defines all points that are 1 inch away from its center, and where your objective is to place all five circles such that their centers are within the triangle or on its boundary, with no circle's center within any other circle.

Divide the larger triangle into four smaller 1 inch equilateral triangles by connecting the midpoints of each of the sides. Note that these 4 triangles completely partition the larger triangle.

Now begin placing your 5 circles over the larger triangle. The center of each circle placed with necessarily fall within one of the smaller triangles, and will completely cover the triangle. Since the circle defines the area within which another circle's center cannot be placed, and there are at most four triangles within which we can place these circles, the fifth circle placed must overlap one of the previous circles. This overlap means that two points will be within 1 inch of each other.
9.26.2005 4:31pm
Kevan Choset (mail):
I think Syd Henderson's solution (here) remains the clearest and most accurate. As mentioned above, Informer's solution ignores the fact that some of those circles will lie outside the rectangle/triangle. And the solutions involving starting with three points at the corner only prove that that one particular way of placing the points doesn't work; they don't prove that there aren't alternative ways.
9.26.2005 5:29pm
Dread Justice Roberts:
Syd is right, but has phrased his answer inconsistently with the puzzle. After drawing the interior equilatoral triangle:

"At least two of the five points must be contained within or on the perimeter of one of the four small triangle, hence are less than one inch apart."(emphasis added)

But this isn't true. If you draw points only at the vertices of the smaller triangles, then there are six points that are exactly 1 inch from the nearest other points. It is only because the puzzle asks for proof that "there will be two points an inch or less" away from one another that it can be solved. The configuration posited shows that the proposition isn't true if you must show that two points are less than an inch away from one another.
9.26.2005 5:48pm
duglmac (mail):
Choose three points that are at a maximum distance from each other within the triangle. Define a set that contains all remaining points further than 1 inch from the corners. It is impossible to choose 2 points from that set that meet the criteria.
9.26.2005 6:47pm
Kevan Choset (mail):
duglmac, 1) Why will a contradictory example necessarily have three of the points at maximum distance from each other? 2) How do you know that it is then impossible to place two more? That's sort of what the initial question is asking you to prove.
9.26.2005 6:57pm
Informer's solution does take into account that some part of the circles will be outside the rectangle...he specifically says that each circle has to have at least 1/4 its area in the triangle (true, since the center must be in the rectangle).

His solution is still wrong; according to his solution, we couldn't fit 5 points >1 inch apart each into a rectangle 2 by sqrt(3), where it's easily possible (1 at each corner and 1 in the center). His solution goes astray when he implicitly assumes that the 1 inch circles can't overlap. They can; they just can't contain the centers of other circles.
9.26.2005 7:15pm
Gah. The first 'triangle' in my above post should read 'rectangle' instead. The first 'rectangle' in my above post should read 'rectangle/triangle'. Sigh.
9.26.2005 7:17pm
mbeadles (mail):
Kevin, I have got a triangle here which meets your criteria, but for which your conjecture cannot be proven true; in fact it can be proven false. I can draw as many distinct points as I like, and they are all more than one inch from each other.

Of course, MY triangle lies in a non-Euclidean space. You DID leave that loophole.
9.26.2005 8:03pm
Bruce Hayden (mail) (www):
I was originally doing it with circles, and that works. But triangles seem to work faster. Start with four equalateral triangles one inch to a side. Each point within each triangle is within one inch of each other because the hypotenuse is sqrt(3)/2. You then arrange the four triangles within the larger triangle so that they don't overlap, because if they do, then you have two points within one inch of each other. There is, of course, only one way to fit all four triangles in within the larger triangle without them overlapping, and that is when they take up the entire larger triangle - which is obvious since the area of the larger triangle is four times that of the smaller ones (double the length and double the height). Then, any other point is going to be within one of the four triangles (or on its edge, which also counts).
9.26.2005 11:20pm
Bruce Hayden (mail) (www):
Well, as I look at my triangles, I think I still need the circles - one one inch radius circle per triangle. The goal is to leave some part of the big triangle uncovered by four one inch circles. So, to maximize the amount of area left in the middle when placing three circles, you put them at the vertices. You then chop off the parts of the circles outside the big triangle, and draw a straight line between where the circles intersect the large triangle. This gives three one inch per side equalateral triangles arranged in the three corners of the big triangle, with the center open. But that forms a fourth identical triangle (upside down), and, thus, every point in that fourth triangle is within an inch of each other point in it, and is thus within any circle of radius one with its center within the middle triangle. So, you can't arrange the four circles without overlapping the entire large triangle, and thus any other point is going to be within one one of these four circles, and thus within one inch of another point.
9.27.2005 12:02am
I have discovered a marvelous proof to this theorem, that this blog is too narrow to contain.
9.27.2005 5:06pm
Paul Dietz (mail):
Syd Henderson's proof uses the Pigeonhole Principle, which is useful in many combinatorial proofs.
9.27.2005 5:16pm