BMAD Posted March 24, 2015 Report Share Posted March 24, 2015 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. Quote Link to comment Share on other sites More sharing options...

0 gavinksong Posted March 24, 2015 Report Share Posted March 24, 2015 1/2 Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted March 24, 2015 Report Share Posted March 24, 2015 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. Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted March 24, 2015 Report Share Posted March 24, 2015 Previous post is incorrect. 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 41 1 2 3 42 2 2 x y3 3 x 3 y4 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 Quote Link to comment Share on other sites More sharing options...

0 k-man Posted March 25, 2015 Report Share Posted March 25, 2015 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. Quote Link to comment Share on other sites More sharing options...

0 Rainman Posted March 26, 2015 Report Share Posted March 26, 2015 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. Quote Link to comment Share on other sites More sharing options...

0 phil1882 Posted March 26, 2015 Report Share Posted March 26, 2015 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. Quote Link to comment Share on other sites More sharing options...

## Question

## BMAD

## Link to comment

## Share on other sites

## 6 answers to this question

## Recommended Posts

## Join the conversation

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