Let A1A2...A99 be a regular 99−gon and point A100 be its center. find the smallest possible natural number n , such that Parsa can color all segments AiAj ( 1≤i<j≤100 ) with one of n colors in such a way that no two homochromatic segments intersect each other or share a vertex. Proposed by Josef Tkadlec - Czech Republic
Problem
Source: Iran Team selection test 2024 - P6
Tags: combinatorics
26.05.2024 01:54
The answer is 132. Bound: A segment containing the central point is called a stick A diagonal segment of maximal length is called a long segment A diagonal segment of the second longest length is called a medium segment Notice that no two sticks or long segments can be the same color and no three medium segments can be the same color. Also, a stick, a long segment, and a medium segment can not all be the same color. Finally, two medium segments and a long segment can not all be the same color. That means one color is able to color at most one stick and two medium segments or two of any of the above types of segments. Algebraically, we want to find the minimum number of triples of the form (2,1,0), (1,0,1), or (0,1,1) such that each component of the sum is at least 99. A very elementary argument shows that we need at least 132 triplets. Construction: It is not hard to partition the 99 sticks, medium segments, and long segments into 33 pairs of two sticks and one medium segment that do not intersect, 33 pairs of a stick and a long segment that do not intersect, and 66 pairs of a medium and a long segment that do not intersect (This is rather tedious but straightforward to provide a construction). Now color each of these groups one of 132 colors. Notice that each segment smaller than a medium segment is parallel to a medium or long segment and is contained in it's smaller arc. To finish the construction simply color each of these smaller segments the same color as the segment described previously. This clearly avoids intersections.
28.05.2024 03:40
Can any verify if that is the correct answer?
28.05.2024 04:31
Yes, 4n/3 is the correct answer. But I have not gone through the details of the solution above, so I don't know if the argument is correct.