Kan Krao Park is a circular park that has $21$ entrances and a straight line walkway joining each pair of two entrances. No three walkways meet at a single point. Some walkways are paved with bricks, while others are paved with asphalt. At each intersection of two walkways, excluding the entrances, is planted lotus if the two walkways are paved with the same material, and is planted waterlily if the two walkways are paved with different materials. Each walkway is decorated with lights if and only if the same type of plant is placed at least $45$ different points along that walkway. Prove that there are at least $11$ walkways decorated with lights and paved with the same material.
Problem
Source: 2021 Thailand MO P4
Tags: combinatorics, pigeonhole principle
01.12.2021 07:35
Let these $21$ entrances be $A_1,A_2,...,A_{21}$ in a clockwise order. Since no three walkways meet at a single point, there are $9\cdot10=90$ plants on walkway $A_1A_{11}$. By pigeonhole principle., there are at least $\left\lceil \frac{90}{2} \right\rceil=45$ same type of plant on $A_1A_{11}$. Thus walkway $A_1A_{11}$ is decorated with lights. Similarly, walkway $A_2A_{12},A_3A_{13},...,A_{21}A_{10}$ are also decorated with lights. So, there are at least $21$ walkways that are decorated with lights. By pigeonhole principle., there are at least $\left\lceil \frac{21}{2} \right\rceil=11$ walkways that are decorated with lights and paved with the same material.
Attachments:

02.12.2021 05:13
Label the $21$ entrances by $1,2,\dots,21$ in that order and a walkway joining entrances $a,b$ by $(a,b)$. Note that the walkways$(n,n+10)$ and $(n,n+11)$ has exactly $9\times 10=90$ plants. By the Pigeonhole principle, There exist one type of plant with at least $45$ plants in that walkway. So that walkway is decorated with lights. Lastly, There are at least $21$ walkways $(1,11),(2,12),\dots,(21,10)$ decorated with lights. Again, by the pigeonhole principle There are at least $11$ walkways decorated with lights and paved with the same material.
02.06.2022 08:28
Let the entrances be $A_0,A_1,\dots,A_{20}.$ Consider the pathway $A_iA_{i+10},$ where indices are taken modulo $21.$ There are $9\cdot 10$ other paths that intersect with $A_iA_{i+10}$ so at least $45$ of the paths must be the same or at least $45$ of the paths must be different by pigeonhole; in either case, at least $45$ of the same flower is planted on the path so the path is lit. Notice this is true for all $A_iA_{i+10}$ for $0\le i\le 10$ and for all $A_iA_{i+11}$ for $0\le i\le 9.$ Hence, there are $21$ paths with lights, and by pigeonhole at least $11$ must be of the same material. $\square$