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
Problem
Source: Macedonian Mathematical Olympiad 2023 P5
Tags: combinatorics
15.04.2023 16:41
Bumping this thread
15.04.2023 17:51
# redacted
15.04.2023 18:04
@above this isn't correct, as it turns out the worst possible distribution is not the alternating one. The worst config i've found is
15.04.2023 18:07
MathSaiyan wrote: @above this isn't correct, as it turns out the worst possible distribution is not the alternating one. The worst config i've found is
I see I thought the swap was not restricted to adjacency my bad.
16.04.2023 00:04
This was a cruel problem to actually give on the test, but alright. $\color{black} \rule{7.4cm}{1pt}$ We claim that the desired maximum is $\boxed{n-2}$. To achieve this entropy, consecutively place around the table: $1$ boy (Bob), $\left\lfloor\frac{n-1}{2}\right\rfloor$ girls (block G1), $\left\lceil\frac{n-1}{2}\right\rceil$ boys (block B2), $1$ girl (Alice), $\left\lfloor\frac{n-1}{2}\right\rfloor$ boys (block B1) and $\left\lceil\frac{n-1}{2}\right\rceil$ girls (block G2).
$\color{black} \rule{7.4cm}{1pt}$ Now, we show that every starting configuration can be resolved in at most $n-2$ steps. To begin, some definitions: block - a group of people of the same gender sat consecutively around the table (we assume that blocks are maximal, i.e., that every person that is of the same gender as, and neighbors a person in the block also belongs to the block) island - a block containing only one person run - a series of two or more islands that are sat consecutively around the table (we also assume that runs are maximal) resolve (a group of people) - perform a series of swaps that bring every person from the group next to a neighbor of the same gender Note that the total number of boy blocks must be equal to the total number of girl blocks. Lemma: Let a given run contain $g$ girls. Then, it can be resolved in at most $g$ steps.
The cases when there are at most three boy blocks can be checked by casework on the numbers of boy islands and girls islands (the details are boring to write out, but in general the cases can be resolved in at most $n-2$ steps by directly moving the islands towards another island of the same gender, if it exists, and to a block of the same gender if it doesn't; just about the only problematic case for this strategy is exactly the above maximal configuration). Furthermore, note the case when there are only islands around the table can be resolved in $\left\lceil\frac{n}{2}\right\rceil$ steps by just going around the circle and greedily swapping pairs of consecutive islands when we encounter them, and (if $n{}$ is odd) using the final move to connect the last remaining islands with people of the same gender. Thus, from here onwards we assume that there are at least $4$ distinct boy regions, not all of which are islands. Note that it is impossible to have exactly $n-1$ islands of a given gender, so our starting configuration can have at most $n-2$ islands of either gender. The following process is the crux of our proof: Gender_Connect Algorithm (GC) (for boys): Starting from a non-island boy region and going clockwise, enumerate the girl regions encountered $1,2,...$, and let the $i{}$-th girl region consist of $a_i$ girls. Let $A=\{i\mid \text{girl region }i\text{ neighbors at least one boy island and }i\text{ is even}\}$ and $B=\{i\mid \text{girl region }i\text{ neighbors at least one boy island and }i\text{ is odd}\}$. Also, let $S_1=\sum_{i\in A}a_i$ and $S_2=\sum_{i\in B}a_i$. Since $S_1+S_2\le \text{total number of girls}=n$, at least one of them must be $\leq \frac{n}{2}$. Algorithm: we move the boy islands through whichever of the two girl regions it neighbors is a part of the smaller $S_j$ (if $S_1=S_2=\frac{n}{2}$, then we can move the boy islands either only through even-numbered girl regions or only through odd-numbered ones). Notice that that GC can resolve all boys (and by applying a similar algorithm - all girls) in at most $\frac{n}{2}$ steps. Also see that if we apply GC to one gender, by its end it can never create a new island of the other gender, only resolve already existing islands. In hopes of solving the problem, we apply GC twice - first to whichever gender would require the smaller amount of steps to resolve by GC, and then, in the resulting configuration, to the other. Suppose that these two processes in total take more than $n-2$ steps. We look at three possible cases: $n{}$ is even and the first application of GC does $n/2$ moves
$n{}$ is even, the first GC takes $n/2-1$ moves, and the second $n/2$ moves
$n{}$ is odd and both GCs take $(n-1)/2$ moves
Thus, every configuration can be resolved in at most $n-2$ steps. $\blacksquare$
18.04.2023 20:40
Thanks for sharing your solution. Has anyone managed to come up with something along the lines of a monovariant, some closed form utility (or equivalently penalty) function?