Return to Answer

Edit. The approach I originally suggested, that is, leveraging Lemma 1 below to carry a case analysis, isn't as promising as I thought. In this updated "answer" I provide a detailed proof of the following proposition:

Denoting by $m(k, n)$ the minimum number of swaps required in the worst case, the above proposition yields $$m(4, n) \le \frac{23}{12}n.$$

Our proof follows the ordering based approach suggested by the OP at the bottom of his post.

Proof. We proceed by induction on $k \ge 1$. If $k = 1$, the result is obvious. Let us assume that $k > 1$ and let $(a_l)_{1 \le l \le kn}$ be the sequence of real numbers which consists of the elements of $\bigsqcup_{i = 1}^k A_i$ sorted in increasing order. For $i \in \{1, \dots, k\}$, we define $A_i' = \{ a_l \,\vert\, l \equiv i \mod k \}$ which is a multiset of size $n$. For every $i, j \in \{1, \dots, k\}$ such that $i < j$, we observe that $\sigma(A_j') - a_{(k - 1)n + j} \le \sigma(A_i') \le \sigma(A_j')$ so that $\vert \sigma(A_i') - \sigma(A_j') \vert \le 1$ for every $i, j\in \{1, \dots, k\}$. As $\bigsqcup_{i = 1}^k A_i = \bigsqcup_{i = 1}^k A_i'$, there is at least one integer $i \in \{1, \dots, k\}$ such that $\vert A_i \cap A_1' \vert \ge \frac{n}{k}$. We can assume, without loss of generality that $i = 1$. After turning $A_1$ in to $A_1'$ by means of at most $\lfloor \frac{(k - 1)n}{k} \rfloor$, we can apply the induction hypothesis to the multisets $A_2, \dots, A_k$, which completes the proof.

Claim. We have $\mu(2, n) = \lfloor \frac{n}{2} \rfloor$ and $n - 2 \le \mu(3, n) \le n$.

Poof. Proving the identity $\mu(2, n) = \lfloor \frac{n}{2} \rfloor$ is straightforward. Let us show that $\mu(3, n) \le n$. Let $r_i, g_i$ and $b_i$ be respectively the number of red, green and blue balls in the $i$-th bin for $i \in \{1, 2, 3\}$. Relabelling the bins and permuting the colours if needed, we can assume that $r_1 = \max \{r_i, g_i, b_i \, \vert \, i =1, 2, 3\}$. Since $g_1 + b_1 = r_2 + r_3$, we may assume, without loss of generality that (1) $g_1 \le r_2$ or (2) $b_1 \le r_2$ (simply observe that $\min(g_1, b_1) \le \max(r_2, r_3)$). We shall address the case (1) only, as (2) is similar. We perform $g_1 + b_1$ swaps to turn the first bin into a red monochrome in such a way that the $g_1$ green balls of the first bin go into the second bin. Now the second bin contains $g_1 + g_2$ green balls so that it takes $g_3$ swaps to render it green monochrome. Since $g_3 \le r_1$, the case (1) is settled. To show that $\mu_(3, n) \ge n - 2$, it suffices to consider the filling for which the distribution of colours in each bin is the closest from the uniform distribution.

Corollary. We have $\frac{2}{3}n \le m(3, n) \le n$.

Edit. The approach I originally suggested, that is, leveraging Lemma 1 below to carry a case analysis, isn't as promising as I thought. In this updated "answer", we show the following:

Denoting by $m(k, n)$ the minimum number of swaps required in the worst case, the above proposition yields $$m(4, n) \le \frac{23}{12}n,$$

a bound that is subsequently improved in the corollary below, showing that $$m(4, n) \le \frac{7}{4}n.$$

Note. At the moment of writing, the most promising approach seems to be Tony Huynh's case analysis, as we expect it to yield $m(4, n) \le n$, i.e., the bound conjectured by the OP.

Our proof of the above proposition follows the ordering based approach suggested by the OP at the bottom of his post.

Proof of the proposition. We proceed by induction on $k \ge 1$. If $k = 1$, the result is obvious. Let us assume that $k > 1$ and let $(a_l)_{1 \le l \le kn}$ be the sequence of real numbers which consists of the elements of $\bigsqcup_{i = 1}^k A_i$ sorted in increasing order. For $i \in \{1, \dots, k\}$, we define $A_i' = \{ a_l \,\vert\, l \equiv i \mod k \}$ which is a multiset of size $n$. For every $i, j \in \{1, \dots, k\}$ such that $i < j$, we observe that $\sigma(A_j') - a_{(k - 1)n + j} \le \sigma(A_i') \le \sigma(A_j')$ so that $\vert \sigma(A_i') - \sigma(A_j') \vert \le 1$ for every $i, j\in \{1, \dots, k\}$. As $\bigsqcup_{i = 1}^k A_i = \bigsqcup_{i = 1}^k A_i'$, there is at least one integer $i \in \{1, \dots, k\}$ such that $\vert A_i \cap A_1' \vert \ge \frac{n}{k}$. We can assume, without loss of generality that $i = 1$. After turning $A_1$ in to $A_1'$ by means of at most $\lfloor \frac{(k - 1)n}{k} \rfloor$, we can apply the induction hypothesis to the multisets $A_2, \dots, A_k$, which completes the proof.

Claim. We have $\mu(2, n) = \lfloor \frac{n}{2} \rfloor$ , $n - 2 \le \mu(3, n) \le n$ and $\frac{3}{2}n - 3 \le \mu(4, n) \le \frac{7}{4}n$.

Poof. Proving the identity $\mu(2, n) = \lfloor \frac{n}{2} \rfloor$ is straightforward. Let us show that $\mu(3, n) \le n$. Let $r_i, g_i$ and $b_i$ be respectively the number of red, green and blue balls in the $i$-th bin for $i \in \{1, 2, 3\}$. Relabelling the bins and permuting the colours if needed, we can assume that $r_1 = \max \{r_i, g_i, b_i \, \vert \, i =1, 2, 3\}$. Since $g_1 + b_1 = r_2 + r_3$, we may assume, without loss of generality that (1) $g_1 \le r_2$ or (2) $b_1 \le r_2$ (simply observe that $\min(g_1, b_1) \le \max(r_2, r_3)$). We shall address the case (1) only, as (2) is similar. We perform $g_1 + b_1$ swaps to turn the first bin into a red monochrome in such a way that the $g_1$ green balls of the first bin go into the second bin. Now the second bin contains $g_1 + g_2$ green balls so that it takes $g_3$ swaps to render it green monochrome. Since $g_3 \le r_1$, the case (1) is settled. To show that $\mu(3, n) \ge n - 2$, it suffices to consider the filling for which the distribution of colours in each bin is the closest from the uniform distribution. To show that $\mu(4, n) \le \frac{7}{4}$, we make one of the four bins monochrome by means of at most $\lfloor \frac{3}{4}n \rfloor$ swaps and makes the three remaining bins monochrome by means of at most $n$ swaps.

Corollary. We have $\frac{2}{3}n - 1 \le m(3, n) \le n$ and $n - 1 \le m(4, n) \le \frac{7}{4}n$.

Proof. The upper bounds are a direct consequence of the problem reduction and the lower bounds are obtained by considering one multiset (resp. two multisets) with $n$ ones and other multisets made of zeros.

This gives us a proven upper bound of at most $\frac{23}{12}n$ swaps in the case of $4$ multisets.

Our proof follows the approach suggested by the OP at the bottom of his post.

Proof. We proceed by induction on $k \ge 1$. If $k = 1$, the result is obvious. Let us assume that $k > 1$ and let $(a_l)_{1 \le l \le kn}$ be the sequence of real numbers which consists of the elements of $\bigsqcup_{i = 1}^k A_i$ sorted in increasing order. For $i \in \{1, \dots, k\}$, we define $A_i' = \{ a_l \,\vert\, l \equiv i \mod k \}$ which is a multiset of size $n$. For every $i, j \in \{1, \dots, k\}$ such that $i < j$, we observe that $\sigma(A_j') - a_{(k - 1)n + j} \le \sigma(A_i') \le \sigma(A_j')$ so that $\vert \sigma(A_i') - \sigma(A_j') \vert \le 1$ for every $i, j\in \{1, \dots, k\}$. As $\bigsqcup_{i = 1}^k A_i = \bigsqcup_{i = 1}^k A_i'$, there is at least one integer $i \in \{1, \dots, k\}$ such that $\vert A_i \cap A_1' \vert \ge \frac{n}{k}$. We can assume, without loss of generality that $i = 1$. After turning $A_1$ in to $A_1'$ by means of at most $\lfloor \frac{(k - 1)n}{k} \rfloor$, we can apply the induction hypothesis to the multisets $A_2, \dots, A_k$, which completes the proof.

Denoting by $m(k, n)$ the minimum number of swaps required in the worst case, the above proposition yields $$m(4, n) \le \frac{23}{12}n.$$

Our proof follows the ordering based approach suggested by the OP at the bottom of his post.

Proof. We proceed by induction on $k \ge 1$. If $k = 1$, the result is obvious. Let us assume that $k > 1$ and let $(a_l)_{1 \le l \le kn}$ be the sequence of real numbers which consists of the elements of $\bigsqcup_{i = 1}^k A_i$ sorted in increasing order. For $i \in \{1, \dots, k\}$, we define $A_i' = \{ a_l \,\vert\, l \equiv i \mod k \}$ which is a multiset of size $n$. For every $i, j \in \{1, \dots, k\}$ such that $i < j$, we observe that $\sigma(A_j') - a_{(k - 1)n + j} \le \sigma(A_i') \le \sigma(A_j')$ so that $\vert \sigma(A_i') - \sigma(A_j') \vert \le 1$ for every $i, j\in \{1, \dots, k\}$. As $\bigsqcup_{i = 1}^k A_i = \bigsqcup_{i = 1}^k A_i'$, there is at least one integer $i \in \{1, \dots, k\}$ such that $\vert A_i \cap A_1' \vert \ge \frac{n}{k}$. We can assume, without loss of generality that $i = 1$. After turning $A_1$ in to $A_1'$ by means of at most $\lfloor \frac{(k - 1)n}{k} \rfloor$, we can apply the induction hypothesis to the multisets $A_2, \dots, A_k$, which completes the proof.

In the above proof, we have reduced OP's problem to the following:

Problem. Let $k$ sets with $n$ balls be such that balls in the same set have the same colour and distinct sets have distinct colours. Fill $k$ bins of capacity $n$ with the $kn$ coloured balls. In the worst case, what is the smallest number $\mu(k, n)$ of swaps that render all bins monochrome?

Thanks to the problem reduction, we have $$m(k, n) \le \mu(k, n)$$ and the proposition yields $$\mu(k, n) \le (k - H(k))n$$ where $H(k) := 1 + \frac{1}{2} + \cdots + \frac{1}{k}$.

Claim. We have $\mu(2, n) = \lfloor \frac{n}{2} \rfloor$ and $n - 2 \le \mu(3, n) \le n$.

Poof. Proving the identity $\mu(2, n) = \lfloor \frac{n}{2} \rfloor$ is straightforward. Let us show that $\mu(3, n) \le n$. Let $r_i, g_i$ and $b_i$ be respectively the number of red, green and blue balls in the $i$-th bin for $i \in \{1, 2, 3\}$. Relabelling the bins and permuting the colours if needed, we can assume that $r_1 = \max \{r_i, g_i, b_i \, \vert \, i =1, 2, 3\}$. Since $g_1 + b_1 = r_2 + r_3$, we may assume, without loss of generality that (1) $g_1 \le r_2$ or (2) $b_1 \le r_2$ (simply observe that $\min(g_1, b_1) \le \max(r_2, r_3)$). We shall address the case (1) only, as (2) is similar. We perform $g_1 + b_1$ swaps to turn the first bin into a red monochrome in such a way that the $g_1$ green balls of the first bin go into the second bin. Now the second bin contains $g_1 + g_2$ green balls so that it takes $g_3$ swaps to render it green monochrome. Since $g_3 \le r_1$, the case (1) is settled. To show that $\mu_(3, n) \ge n - 2$, it suffices to consider the filling for which the distribution of colours in each bin is the closest from the uniform distribution.

Corollary. We have $\frac{2}{3}n \le m(3, n) \le n$.

This is a long comment hinting towards a case analysis.

Claim. Let $A, B$ and $C$ be three multisets of size $n$ with all their elements in the interval $[0, 1]$. We can turn these multisets into three multisets $A', B'$ and $C'$ of size $n$ and such that $$\vert \sigma(M) - \sigma(N) \vert \le 1 \text{ for every} M, N \in \{A', B', C'\}$$ by means of at most $\lceil \frac{n}{2} \rceil + \lceil \frac{n}{3} \rceil$ swaps between multiset elements.

Edit. The approach I originally suggested, that is, leveraging Lemma 1 below to carry a case analysis, isn't as promising as I thought. In this updated "answer" I provide a detailed proof of the following proposition:

Proposition. Let $k, n \ge 1$ and let $A_1, \dots, A_k$ be $k$ multisets of size $n$ with all their elements in the interval $[0, 1]$. Then we can turn $A_1, \dots, A_k$ into $k$ multisets $A_1'\, \dots, A_k'$ of size $n$ such that $\vert \sigma(A_i') - \sigma(A_j') \vert \le 1$ for every $i, j\in \{1, \dots, k\}$ by means of at most $\lfloor \frac{n}{2} \rfloor + \lfloor \frac{2n}{3} \rfloor + \cdots + \lfloor \frac{(k - 1)n}{k} \rfloor$ swaps.

This gives us a proven upper bound of at most $\frac{23}{12}n$ swaps in the case of $4$ multisets.

Our proof follows the approach suggested by the OP at the bottom of his post.

Proof. We proceed by induction on $k \ge 1$. If $k = 1$, the result is obvious. Let us assume that $k > 1$ and let $(a_l)_{1 \le l \le kn}$ be the sequence of real numbers which consists of the elements of $\bigsqcup_{i = 1}^k A_i$ sorted in increasing order. For $i \in \{1, \dots, k\}$, we define $A_i' = \{ a_l \,\vert\, l \equiv i \mod k \}$ which is a multiset of size $n$. For every $i, j \in \{1, \dots, k\}$ such that $i < j$, we observe that $\sigma(A_j') - a_{(k - 1)n + j} \le \sigma(A_i') \le \sigma(A_j')$ so that $\vert \sigma(A_i') - \sigma(A_j') \vert \le 1$ for every $i, j\in \{1, \dots, k\}$. As $\bigsqcup_{i = 1}^k A_i = \bigsqcup_{i = 1}^k A_i'$, there is at least one integer $i \in \{1, \dots, k\}$ such that $\vert A_i \cap A_1' \vert \ge \frac{n}{k}$. We can assume, without loss of generality that $i = 1$. After turning $A_1$ in to $A_1'$ by means of at most $\lfloor \frac{(k - 1)n}{k} \rfloor$, we can apply the induction hypothesis to the multisets $A_2, \dots, A_k$, which completes the proof.

The remains of my original answer.

This is a long comment hinting towards a case analysis.

Claim (Not verified, hence possibly wrong). Let $A, B$ and $C$ be three multisets of size $n$ with all their elements in the interval $[0, 1]$. We can turn these multisets into three multisets $A', B'$ and $C'$ of size $n$ and such that $$\vert \sigma(M) - \sigma(N) \vert \le 1 \text{ for every} M, N \in \{A', B', C'\}$$ by means of at most $\lceil \frac{n}{2} \rceil + \lceil \frac{n}{3} \rceil$ swaps between multiset elements.

Note. The proof below is incorrect. Indeed, it actually enforces only two of the three required conditions. For the third condition, we get only an approximation up to $\frac{5}{4}$. It is possible to fix the proof, but at the cost of increasing the number of required swaps in a very disappointing way: $2\lceil \frac{n}{2} \rceil + \lceil \frac{n}{3} \rceil$.