A regular polygon with $20$ vertices is given. Alice colors each vertex in one of two colors. Bob then draws a diagonal connecting two opposite vertices. Now Bob draws perpendicular segments to this diagonal, each segment having vertices of the same color as endpoints. He gets a fish from Alice for each such segment he draws. How many fish can Bob guarantee getting, no matter Alice's goodwill?
Problem
Source: 2023 Israel TST Test 5 P1
Tags: combinatorics, TST, regular polygon
12.04.2023 15:24
The answer is $4$. For an example, paint $2$ adjacent vertices with the same color alternately. Let $a$ be the number of vertices painted with one of the colors, $a \geq 10$ wlog. Let's calc the average number of segments drawned by Bob over all the $10$ simmetry axis in an arbitrary config. If this number is greater than $3$, we are done. Since a segment between two vertices of the same color is drawned in a moment of the sum if and only if there's an odd number of vertices between them, note that for each $3$ vertices of the same color, at least one segment is drawned between two of them, by parity. Making $\binom{a}{3}$, we're counting each of those segments $a-2$ times, one for each other vertex of the same color completing the triple. Then, our average is at least $ \dfrac{\binom{a}{3}}{a-2} \cdot \dfrac{1}{10}$ + $\dfrac{\binom{20-a}{3}}{18-a} \cdot \dfrac{1}{10} = \dfrac{a(a-1)+ (20-a)(19-a)}{60} > 3 \iff$ $ a(a-1)+ (20-a)(19-a) > 180 \iff (a-10)^2 > 0 $. We show that the equality cannot occur for $a=10$. Take a graph where the vertices are the vertices of the same color, and drawn an edge between two vertices if there's an even number of vertices in the regular polygon between them. As we've seen, the graph doesn't have triangles, so for the Mantel's theorem the number of edges is at most $\lfloor \dfrac{10^2}{4} \rfloor = 25$. So we have at least $\binom{10}{2} - 25 = 20$ edges not drawned. But for the equality case we would have $\dfrac{\binom{10}{3}}{10-2} = 15$, contradiction. Hence, Bob can always guarantee more than $3$ fishes and Alice can make Bob take $4$ fishes.