Let $A_1A_2...A_{99}$ be a regular $99-$gon and point $A_{100}$ be its center. find the smallest possible natural number $n$ , such that Parsa can color all segments $A_iA_j$ ( $1 \le i < j \le 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 $\boxed{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.