Problem

Source: Macedonian Mathematical Olympiad 2023 P5

Tags: combinatorics



There are $n$ boys and $n$ girls sitting around a circular table, where $n>3$. In every move, we are allowed to swap the places of $2$ adjacent children. The entropy of a configuration is the minimal number of moves such that at the end of them each child has at least one neighbor of the same gender. Find the maximal possible entropy over the set of all configurations. Proposed by Viktor Simjanoski