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
Makaveli
15.04.2023 16:41
Bumping this thread
khan.academy
15.04.2023 17:51
# redacted
MathSaiyan
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
Taking a girl, $\frac{n-1}{2}$ boys, $\frac{n-1}{2}$ girls, a boy, $\frac{n-1}{2}$ girls, $\frac{n-1}{2}$ boys and going back to the initial girl (this for odd $n$, there's a similar one for even $n$). This requires at least $n-2$ swaps.
khan.academy
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
Taking a girl, $\frac{n-1}{2}$ boys, $\frac{n-1}{2}$ girls, a boy, $\frac{n-1}{2}$ girls, $\frac{n-1}{2}$ boys and going back to the initial girl (this for odd $n$, there's a similar one for even $n$). This requires at least $n-2$ swaps.
I see I thought the swap was not restricted to adjacency my bad.
Math00954
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).
To see that this configuration can be resolved in $n-2$ steps, we will look at the cases where $n$ is even and where it is odd separately. If $n$ is even, then we can simply have Alice swap places with each boy from B1 and Bob - with each girl from G1. On the other hand, if $n$ is odd, then we have the girl from G1 closest to Alice swap places with each boy from B2 consecutively, and then have Bob swap places with everyone remaining in G1.
Now, to see that we need at least this many moves, denote by $m_{A}$ the minimal number of swaps (at a given point in time) that Alice would need to perform to land next to a girl neighbor. Similarly define $m_B$ for Bob. If $2\mid n$, then $m_A+m_B=n-2$ at the beginning, and at any point in time we can decrease either $m_A$ or $m_B$ by at most one, but never both simultaneously. If, however, $2\nmid n$, then $m_A+m_B=n-1$ at the beginning and at each turn we can decrease $m_A$ and $m_B$ by at most $1$, and can decrease both simultaneously only with the first swap.
**The above argument assumes that we don't make any redundant moves, i.e., don't swap two people of the same gender or immediately undo our previous move.
$\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.
Just swap the first two people in the run and apply induction on the remaining part of the run.$\square$
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
WLOG suppose that the first GC was on performed on the boys. Then, since $S_1+S_2=n$ we must have that all odd-numbered girl regions participate is $S_1$ and that all even-numbered girl regions participate in $S_2$. Hence, all girl regions, and thus all girl islands, neighbor at least one boy island. By the assumptions of this case, if we performed GC on the girls first instead of the boys, then we would also get $\frac{n}{2}$ moves, so by a similar argument, all boy islands must neighbor a girl island in the starting configuration. In other words, all islands around the table belong to a run. However, we have, by assumption, that there are at most $n-2$ total girl islands, so we can just resolve every run in $\le n-2$ moves by the Lemma.$\square$
$n{}$ is even, the first GC takes $n/2-1$ moves, and the second $n/2$ moves
Look at the configuration after the first GC, supposing it was done on the girls. By similar logic as the previous case, there cannot be two consecutive non-island boy regions (separated only by a girl region between them) since we would then be able to apply GC once more in such a way that requires fewer than $\frac{n}{2}$ moves (the girl/s that are between these two boy regions would participate in neither of the $S_i$). However, since GC cannot create new islands, this must have been also true for the starting configuration.
Hence, in the starting configuration every girl island must neighbor at least one boy island. Call a boy island that is not part of any run an NRBI (non-run boy island). If there are no NRBIs, then this case is resolved in the same way as the previous.
Otherwise, we apply GC to the boys in the starting configuration, but only perform the moves dictated by GC that contain an NRBI, in that we always move an NRBI towards the other boy. If any such movement would destroy a previously extant run, leaving a girl NRI, then we must have connected the NRBI with a boy that is a part of a run consisting of only two people. In these cases, we do the opposite moves, i.e., we move the other boy towards the NRBI, not vice versa as originally planned. After this, we resolve the remaining runs using the Lemma. Notice that, in this way, every person around the table will be resolved, every girl will participate in at most one swap and at least two girls will not participate in any swaps (that being the girls that are part of a region that neighbors and NRBI at the start, but which do not participate in its movement. Hence, we must have performed at most $n-2$ swaps. $\square$
$n{}$ is odd and both GCs take $(n-1)/2$ moves
Note that if the GC necessitates a minimum of $\frac{n-1}{2}$ moves for both genders at the start, there can be at most one place where there are consecutive non-island boy regions, and between them there must be an NRGI. Similarly, there can be at most one NRBI. Since the other possibilities are covered by similar arguments as the above cases, we assume that there is exactly one NRBI and one NRGI.
GC being defined such as it is, if we WLOG performed the first GC on the boys, the lone NRGI will not be resolved by its end (what is more, we specifically perform the GC where the $a_i$ corresponding to the NRGI does not participate in the chosen $S_j$). Instead, with the second GC it will move towards a near girl region by moving through one of its neighboring boy regions (let this region be $B$). However, because of the nature of the first GC, $B$ will be larger by one person than it was originally. Now, we slightly change the first GC so that either:
--instead of the boy island moving towards $B$, one person from $B$ moves towards the boy island, and in the second GC the NRGI moves through the reduced $B$ (and we perform all other moves the same as dictated by the original GCs), or
-- we slightly rearrange the direction in which we perform the moves in the run neighboring $B$ so that $B$ is not increased and there is a girl island left with which we will connect the NRGI by moving it through (the now-unchanged) $B$ (and we perform all other moves the same as dictated by the original GCs)
This means that we can take the series of $\frac{n-1}{2}$ moves after the first GC and shorten it by one, thus bringing our total number of moves down to $\frac{n-1}{2}+\frac{n-1}{2}-1=n-2$.
Thus, every configuration can be resolved in at most $n-2$ steps. $\blacksquare$
I tried, and failed, to make this coherent; it's a bit clearer if you just draw the situations on paper. The last case (when $n$ is odd) came out confusingly, and is still not completely clear to me, but it should be correct - we do the different reconnections of GC1 depending on the parity of the number of girls (or maybe boys - idk right now) in the described run and can narrowly avoid problems with the movement of other girl islands because of the assumption that we have at least $4$ regions each at the start.
Makaveli
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?