Blastoor wrote: A kingdom has $2021$ towns. All of the towns lie on a circle, and there is a one-way road going from every town to the next $101$ towns in a clockwise order. Each road is colored in one color. Additionally, it is known that for any ordered pair of towns $A$ and $B$ it is possible to find a path from $A$ to $B$ so that no two roads of the path would have the same color. Find the minimal number of road colors in the kingdom. Indentify the towns with elements of $\mathbb{Z}/2021\mathbb{Z}$ and denote the road from $A$ to $B$ by $(A,B)$. To go from $n$ to $n+2020$ you need to use at least 20 roads and the only way using 20 roads is over the path $n,n+101,n+202,\ldots,n+1919,n+2020$. So we need at least 20 colors. If we use 20 colors the roads $(n+101k,n+101(k+1))$ for $k\in\{0,1,\ldots,19\}$ must have different colours. By applying this for $n$ and $n+101$ ge get that the roads $(n,n+101)$ and $(n+2020,n+2121)=(n-1,n+100)$ have the same colour. Thus all roads of lenght 101 have the same colour contradicting our previous results. So we need at least 21 colours. The following construction with 21 colours works. We identify with $\{0,1,\cdots,20\}$ works. Paint all roads from $101k+m$ with $k$ for $k\in\{0,1,\ldots,19\},m\in\{0,1,\ldots,100\}$ and paint all roads from 2021 with 20. A possible path from $A$ to $B$ is the one where you use as long as you can not go directly to $B$ steps of size 101.