Jump to content
BrainDen.com - Brain Teasers
  • 0

Equilateral Triangle: Color and distance



Determine the largest number d such that the following is true:
If the points of the perimeter of an equilateral triangle of side 1 are colored with four colors, then there must be two points of the same color which are at least distance d apart.
Link to comment
Share on other sites

6 answers to this question

Recommended Posts

  • 0

The vertices are fewer in number than the colors, so d is strictly less than unity.

Grouping monocolored points along any side gives segments of length 1/4.

So d is at least 0.25.


0.25 <= d < 1.


That is the result for a unit line segment.


Next consider two sides that share a vertex A.


Label the segments 1, 2, 3, 4 on each of the sides, with segment 1 closest to A.

The smallest distance between pairs of segments defines a symmetrical 4x4 matrix.

Let's consider the sides to have length 4, for convenience.

Then the major diagonal has values 0, 1, 2, 3 and 4.

The full matrix is


      1      2      3      4
 1  0.000  0.866  1.732  2.646
 2  0.866  1.000  1.732  2.598
 3  1.732  1.732  2.000  2.646
 4  2.646  2.598  2.646  3.000.


Consider segment 4.

Its minimum distance from any of the segments on the other side is at least 2.598.

If all four colors are represented on each side, an assumption that may not be justified,

then d > 2.598/4 = 0.6495.

Link to comment
Share on other sites

  • 0

Previous post is incorrect. :huh:


Consider coloring a single side of the triangle.


Break the side into 1/4 segments.

For convenience scale up by a factor 4 so the segments are of length 1.

If we assign a unique color to each segment, we obtain d = 1.

Every other coloring increases d, but no value greater than 1 can be guaranteed.


With the assumption that this gives optimal results for pairs of sides as well:*


Quarter and color each side of the triangle and find the greatest pairwise segment distances.

Letting segment 1 be the closest to the common vertex of their sides, and 4 the farthest,

we obtain:


   1  2  3  4
1  1  2  3  4
2  2  2  x  y
3  3  x  3  y
4  4  y  y  4

where 1 < 2 < x < 3 < y < 4.  Specifically, x = sqrt(7) and y = sqrt(13).


The largest pairwise distance always involves a segment 4.

When paired with segment 1 or 4 of the other side, the distance is 4.

When paired with segment 2 or 3 of the other side, the distance is y.


There are colorings where no segment 4 of one side is paired with 1 or 4 of another side.#

An example is given below. But pairings of 4 with 2 or 3 are unavoidable.

So the largest enforceable distance is y. Scaling back to unit sides,


d = y/4 = sqrt(13)/4 ~ 0.90139...




*This assumption has not been proved.


#Here is a coloring {a, b, c, d} where no pair of segments 1 and 4, or 4 and 4, have the same color.


Color the top vertex a, and clockwise the other vertices b and c.

Beginning at the top, clockwise, the 12 segments are colored:


a d c b // b d a c // c d b a


The pairings are as follows.

They show that y/4 is the greatest spacing, hence that is the value for d:


a b d c  Top vertex (color a) is shared. Colors b and c are y/4 apart.

a d c b


b c d a  Lower right vertex (color b) is shared. Colors c and a are y/4 apart.

b d a c


c a d b  Lower left vertex (color c) is shared. Colors a and b are y/4 apart.

c d b a

Link to comment
Share on other sites

  • 0
I agree with gavinksong

Color each vertex with its own color, then color each side half and half with the same colors as the vertices. Now you have a triangle colored with 3 colors and every point of the same color is within d=1/2 from other points of the same color. The fourth color is a red herring and can be a single point somewhere or a segment  that is shorter than 1/2.

Link to comment
Share on other sites

  • 0

As no proof yet has been provided that the statement is true for d=1/2, consider the vertices and the midpoints. These six points are at least a distance of 1/2 away from each other, and with only four (or even five) colors two of them must be the same color. The coloring suggested by k-man shows that the statement is false for d>1/2.

Link to comment
Share on other sites

  • 0

with 4 colors it would definitely be 1/2.
the goal is to gaurantee 2 points of the same color are that distance apart.
so finding a construction where 1/2 works is not a solution, you have to prove that you can always get 1/2, no matter how you color it with 4 colors.
so we need to find the worst case scenario.
as rainman pointed out each of the midpoints of the triangle are 1/2 distance apart.
since we must cover all three midpoints with some color, and coloring any two midpoints the same color would allow for 1/2, the worst we can we can do is have all 3 midpoints a different color. but then we also need the vertexes of the triangle to be a diffent color than the midpoint to try to prevent 1/2. since we only have 4 colors, and six points to worry about to prevent 1/2, 1/2 is the answer.
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Create New...