witzar 18 Report post Posted July 4, 2013 Each point of the circle is painted either red, blue or green. Prove, that there exists isosceles triangle inscribed in the circle with all its vertices of the same color. Share this post Link to post Share on other sites
0 plasmid 39 Report post Posted July 5, 2013 But I think you're on the right track; it might be impossible to fit 5 points on a regular 13 sided polygon in the circle without forming an isosceles triangle, but I haven't found an elegant way of showing it. Share this post Link to post Share on other sites
0 Yoruichi-san 116 Report post Posted July 5, 2013 If we divide the circumference into 10 equal portions with 10 equally spaced points, then at least 4 of the points must be the same color, and there is no way to pick 4 of the points without 3 of them forming an isosceles triangle. So I see a general principle emerging here. I'm not sure I can completely describe it yet, but to start from the beginning: Any triangle whose points lie on a circle is comprised of three inscribed angles. These angles have corresponding arc lengths, so a necessary and sufficient condition for a inscribed triangle to be isosceles is for two of the arc lengths to be equal. If we put n points on the circle, we can figure out the minimum number of points that must be of the same color, call it k. We can think of 'painting' k of those points the same color as dividing the circle into k pieces. Picking any three points to form a triangle is summing adjacent pieces into three groups. If there is a way of forming three groups such that two groups have the same arc length total, then we have an isosceles triangle. So if there is no way of dividing the circumference into k pieces along the n points such that there is no way of forming three groups in which two of the groups have equal arc length, then there must be an isosceles triangle. For the 2 color case, dividing the circumference into 5 pieces of 2pi/5 rad (72 deg) guaranteed that there was at least 3 points of one color, and there was no way to group the pieces into three groups so that no two groups had the same arc length. For the 3 color case, for uniformly placed n points, n is 10, and k is 4. I'm not sure if there is a way of doing it with non-uniform placement with a smaller n, though... I think this may be generalized further, but I'm not sure...it leaves an interesting exercise Share this post Link to post Share on other sites
0 witzar 18 Report post Posted July 5, 2013 If we divide the circumference into 10 equal portions with 10 equally spaced points, then at least 4 of the points must be the same color, and there is no way to pick 4 of the points without 3 of them forming an isosceles triangle. Label those ten points with digits 0-9 clockwise starting with some point. Suppose points 0, 1, 4, 5 are of the same color. Which three of them form isosceles triangle? Share this post Link to post Share on other sites
0 Yoruichi-san 116 Report post Posted July 5, 2013 Shoot, forgot about non-adjacent groupings . Time for bed...got up way too early this morning...I'll leave it to plasmid . Share this post Link to post Share on other sites
0 TimeSpaceLightForce 11 Report post Posted July 6, 2013 templates for paint-a-point Share this post Link to post Share on other sites
0 TimeSpaceLightForce 11 Report post Posted July 6, 2013 It's a fun puzzle type : for 15 use trial and error by placing 2 random red points.. then color the anti isosceles points white ,then the 3rd red point at random until the 5th has no more slot, looking for more possibilities... not tried the fewer yet. Share this post Link to post Share on other sites
0 witzar 18 Report post Posted July 6, 2013 There is no way to paint vertices of regular 13-gon with three colors without forming monochromatic isosceles triangle. And I don't have an elegant proof. (I was hoping that someone here will find it.) But it can be proved as follows. As it was said before (and according to pigeonhole principle) there will be 5 points of the same color. It is enough to prove that some three of the five form isosceles triangle. Five vertices of regular 13-gon inscribed in circle divide the circle into 5 arcs. We can assign to each arc number of sides of 13-gon that this arc covers. This way each selection of 5 points gives some partition of number 13 with 5 parts. Here is the list of all partitions of 13 with 5 parts: [9, 1, 1, 1, 1] [8, 2, 1, 1, 1] [7, 3, 1, 1, 1] [7, 2, 2, 1, 1] [6, 4, 1, 1, 1] [6, 3, 2, 1, 1] [6, 2, 2, 2, 1] [5, 5, 1, 1, 1] [5, 4, 2, 1, 1] [5, 3, 3, 1, 1] [5, 3, 2, 2, 1] [5, 2, 2, 2, 2] [4, 4, 3, 1, 1] [4, 4, 2, 2, 1] [4, 3, 3, 2, 1] [4, 3, 2, 2, 2] [3, 3, 3, 3, 1] [3, 3, 3, 2, 2] If partition contains three or more equal parts, than two arc of the same length have to be next to each other. Such two arcs give us isosceles triangle, so we can remove all such partitions from the list. The list of partitions to investigate becomes shorter: [7, 2, 2, 1, 1] [6, 3, 2, 1, 1] [5, 4, 2, 1, 1] [5, 3, 3, 1, 1] [5, 3, 2, 2, 1] [4, 4, 3, 1, 1] [4, 4, 2, 2, 1] [4, 3, 3, 2, 1] Now observe that each partition of type ababc also gives isosceles triangle, because the only order of parts that avoids two a's next to each other and two b's next to each other contains abab pattern, but in such case there are two arcs of length (a+b) next to each other. Removing such partitions leaves us with four partitions to investigate: [6, 3, 2, 1, 1] [5, 4, 2, 1, 1] [5, 3, 2, 2, 1] [4, 3, 3, 2, 1] These partitions can be investigated one by one. Let's investigate [6, 3, 2, 1, 1]. The only way to avoid two 1's next to each other is to go with the sequence (6, 1, x, 1, y). (Two sequences are equivalent if one can be produced from the other using any combination of circular shifts and/or reversals.) Second 1 is surrounded by 2 and 3, so there are two arcs of lenght 3 (2+1=3) next to each other. Let's investigate [5, 4, 2, 1, 1]. The only way to avoid two 1's next to each other is to go with the sequence (5, 1, x, 1, y). No matter where we choose to put 4, there will be two arcs of length 5 (4+1=5) next to each other. Let's investigate [5, 3, 2, 2, 1]. The only way to avoid two 2's next to each other is to go with the sequence (5, 2, x, 2, y). Second 2 is surrounded by 1 and 3, so there are two arcs of lenght 3 (1+2=3) next to each other. Let's investigate [4, 3, 3, 2, 1]. The only way to avoid two 3's next to each other is to go with the sequence (4, 3, x, 3, y). No matter where we choose to put 1, there will be two arcs of length 4 (3+1=4) next to each other. This concludes the proof. Share this post Link to post Share on other sites
0 bonanova 76 Report post Posted July 6, 2013 There is no way to paint vertices of regular 13-gon with three colors without forming monochromatic isosceles triangle. And I don't have an elegant proof. (I was hoping that someone here will find it.) But it can be proved as follows. As it was said before (and according to pigeonhole principle) there will be 5 points of the same color. It is enough to prove that some three of the five form isosceles triangle. Five vertices of regular 13-gon inscribed in circle divide the circle into 5 arcs. We can assign to each arc number of sides of 13-gon that this arc covers. This way each selection of 5 points gives some partition of number 13 with 5 parts. Here is the list of all partitions of 13 with 5 parts: [9, 1, 1, 1, 1] [8, 2, 1, 1, 1] [7, 3, 1, 1, 1] [7, 2, 2, 1, 1] [6, 4, 1, 1, 1] [6, 3, 2, 1, 1] [6, 2, 2, 2, 1] [5, 5, 1, 1, 1] [5, 4, 2, 1, 1] [5, 3, 3, 1, 1] [5, 3, 2, 2, 1] [5, 2, 2, 2, 2] [4, 4, 3, 1, 1] [4, 4, 2, 2, 1] [4, 3, 3, 2, 1] [4, 3, 2, 2, 2] [3, 3, 3, 3, 1] [3, 3, 3, 2, 2] If partition contains three or more equal parts, than two arc of the same length have to be next to each other. Such two arcs give us isosceles triangle, so we can remove all such partitions from the list. The list of partitions to investigate becomes shorter: [7, 2, 2, 1, 1] [6, 3, 2, 1, 1] [5, 4, 2, 1, 1] [5, 3, 3, 1, 1] [5, 3, 2, 2, 1] [4, 4, 3, 1, 1] [4, 4, 2, 2, 1] [4, 3, 3, 2, 1] Now observe that each partition of type ababc also gives isosceles triangle, because the only order of parts that avoids two a's next to each other and two b's next to each other contains abab pattern, but in such case there are two arcs of length (a+b) next to each other. Removing such partitions leaves us with four partitions to investigate: [6, 3, 2, 1, 1] [5, 4, 2, 1, 1] [5, 3, 2, 2, 1] [4, 3, 3, 2, 1] These partitions can be investigated one by one. Let's investigate [6, 3, 2, 1, 1]. The only way to avoid two 1's next to each other is to go with the sequence (6, 1, x, 1, y). (Two sequences are equivalent if one can be produced from the other using any combination of circular shifts and/or reversals.) Second 1 is surrounded by 2 and 3, so there are two arcs of lenght 3 (2+1=3) next to each other. Let's investigate [5, 4, 2, 1, 1]. The only way to avoid two 1's next to each other is to go with the sequence (5, 1, x, 1, y). No matter where we choose to put 4, there will be two arcs of length 5 (4+1=5) next to each other. Let's investigate [5, 3, 2, 2, 1]. The only way to avoid two 2's next to each other is to go with the sequence (5, 2, x, 2, y). Second 2 is surrounded by 1 and 3, so there are two arcs of lenght 3 (1+2=3) next to each other. Let's investigate [4, 3, 3, 2, 1]. The only way to avoid two 3's next to each other is to go with the sequence (4, 3, x, 3, y). No matter where we choose to put 1, there will be two arcs of length 4 (3+1=4) next to each other. This concludes the proof. Nice puzzle. I figured the number of points should be odd, to make other points become candidate pairs once a vertex was chosen. I was able to confirm 9 points were not enough. I fell asleep exploring 11. Nice solve as well! Share this post Link to post Share on other sites
0 TimeSpaceLightForce 11 Report post Posted July 6, 2013 There is no way to paint vertices of regular 13-gon with three colors without forming monochromatic isosceles triangle. And I don't have an elegant proof. (I was hoping that someone here will find it.) But it can be proved as follows. As it was said before (and according to pigeonhole principle) there will be 5 points of the same color. It is enough to prove that some three of the five form isosceles triangle. Five vertices of regular 13-gon inscribed in circle divide the circle into 5 arcs. We can assign to each arc number of sides of 13-gon that this arc covers. This way each selection of 5 points gives some partition of number 13 with 5 parts. Here is the list of all partitions of 13 with 5 parts: [9, 1, 1, 1, 1] [8, 2, 1, 1, 1] [7, 3, 1, 1, 1] [7, 2, 2, 1, 1] [6, 4, 1, 1, 1] [6, 3, 2, 1, 1] [6, 2, 2, 2, 1] [5, 5, 1, 1, 1] [5, 4, 2, 1, 1] [5, 3, 3, 1, 1] [5, 3, 2, 2, 1] [5, 2, 2, 2, 2] [4, 4, 3, 1, 1] [4, 4, 2, 2, 1] [4, 3, 3, 2, 1] [4, 3, 2, 2, 2] [3, 3, 3, 3, 1] [3, 3, 3, 2, 2] If partition contains three or more equal parts, than two arc of the same length have to be next to each other. Such two arcs give us isosceles triangle, so we can remove all such partitions from the list. The list of partitions to investigate becomes shorter: [7, 2, 2, 1, 1] [6, 3, 2, 1, 1] [5, 4, 2, 1, 1] [5, 3, 3, 1, 1] [5, 3, 2, 2, 1] [4, 4, 3, 1, 1] [4, 4, 2, 2, 1] [4, 3, 3, 2, 1] Now observe that each partition of type ababc also gives isosceles triangle, because the only order of parts that avoids two a's next to each other and two b's next to each other contains abab pattern, but in such case there are two arcs of length (a+b) next to each other. Removing such partitions leaves us with four partitions to investigate: [6, 3, 2, 1, 1] [5, 4, 2, 1, 1] [5, 3, 2, 2, 1] [4, 3, 3, 2, 1] These partitions can be investigated one by one. Let's investigate [6, 3, 2, 1, 1]. The only way to avoid two 1's next to each other is to go with the sequence (6, 1, x, 1, y). (Two sequences are equivalent if one can be produced from the other using any combination of circular shifts and/or reversals.) Second 1 is surrounded by 2 and 3, so there are two arcs of lenght 3 (2+1=3) next to each other. Let's investigate [5, 4, 2, 1, 1]. The only way to avoid two 1's next to each other is to go with the sequence (5, 1, x, 1, y). No matter where we choose to put 4, there will be two arcs of length 5 (4+1=5) next to each other. Let's investigate [5, 3, 2, 2, 1]. The only way to avoid two 2's next to each other is to go with the sequence (5, 2, x, 2, y). Second 2 is surrounded by 1 and 3, so there are two arcs of lenght 3 (1+2=3) next to each other. Let's investigate [4, 3, 3, 2, 1]. The only way to avoid two 3's next to each other is to go with the sequence (4, 3, x, 3, y). No matter where we choose to put 1, there will be two arcs of length 4 (3+1=4) next to each other. This concludes the proof. Nice puzzle. I figured the number of points should be odd, to make other points become candidate pairs once a vertex was chosen. I was able to confirm 9 points were not enough. I fell asleep exploring 11. Nice solve as well! You can say that placing any colored point between any 2 points on plasmid figure of Y-san 10 points will render the isosceles. 443 works Share this post Link to post Share on other sites
Each point of the circle is painted either red, blue or green.
Prove, that there exists isosceles triangle inscribed in the circle with all its vertices of the same color.
Share this post
Link to post
Share on other sites