Skip to main content
7 of 7
Highlight the best upper bound up to now (although it's certainly far from optimal, see Tony Huyn's lead and OP's conjecture)
Luc Guyot
  • 7.9k
  • 2
  • 30
  • 51

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:

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.

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.

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$ , $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.


The remains of my original answer.

This is a long comment hinting towards a case analysis.

Given a finite multiset $A$ consisting of real numbers, we denote by $\sigma(A)$ the sum of its elements.

We settle below the case of two multisets. The details (which are likely to be well-known) are then used to provide a non-trivial upper bound in the case of three multisets. They could also be used to conduct a case analysis in the situation of four multisets.

Lemma 1. Let $A$ and $B$ be two multisets of size $n$ with all their elements in $[0, 1]$ and such that $\sigma(A) \ge \sigma(B)$. Let $\lambda \in [0, 1]$. Then we can turn $A$ into a multiset $A'$ of size $n$ such that $$\vert \sigma(A') - ((1 - \lambda) \sigma(A) + \lambda \sigma(B)) \vert \le \frac{1}{2}$$ by swapping at most $\lceil \lambda n\rceil$ elements of $A$ with some elements of $B$.

Proof. Sort $A$ in decreasing order and let $M_i$ be the $i$-th term of the sorted sequence. Sort $B$ in increasing order and let $m_i$ be the $i$-th term of the sorted sequence. Let $s_0 = \sigma(A)$, and for $i \ge 1$, let $s_i$ be the sum of the elements of the multiset $A'_i$ obtained from $A$ by swapping $M_1, \dots, M_i$ with $m_1, \dots, m_i$ respectively. The $i$-th second order finite difference $\Delta_2(s_i)$ of $(s_j)_{0 \le j \le n}$ is $$m_{i + 1} - m_i - (M_{i + 1} - M_i),$$ which is non-negative for every $i \in \{0, \dots, n - 2\}$. Therefore the piecewise linear interpolation $s$ of $(s_j)_{0 \le j \le n}$ on $[0, n]$ is a convex function. As $s$ satisfies $s(0) = \sigma(A)$ and $s(n) = \sigma(B)$, the convexity of $s$ implies that $s(\lambda n) \le \mu$ where $\mu := (1 - \lambda) \sigma(A) + \lambda \sigma(B)$. To complete the proof, we consider $x_{\mu} := \inf \{ x \in [0, 1] \,\vert\, s(x) > \mu\}$. Since $\vert s_{i + 1} - s_i\vert \le 1$ for every $i \in \{0, \dots, n -1\}$, at least one of $A_{\lfloor{x_{\mu}} \rfloor}$ and $A_{\lceil{x_{\mu}} \rceil}$ is at distance at most $\frac{1}{2}$ of $\mu$.

Lemma 2. Let $a, b$ and $c$ be non-zero real numbers such that $a + b + c = 0$. There is a permutation $\theta$ of the letters $\{a, b, c\}$ such that $\left\vert \frac{\theta(a)}{ \theta(b)} \right\vert \ge 2.$

Proof. Renaming the variables if needed, can assume that $b$ and $c$ have the same sign and that $\vert b \vert \le \vert c \vert$. The result now follows from the identity $\left\vert\frac{a} {b} \right\vert = 1 + \left\vert\frac{c} {b} \right\vert$.

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$.

Proof. Let $S = \sigma(A) + \sigma(B) + \sigma(C)$. Let us assume first that $\sigma(A) = \frac{S}{3}$. Renaming the multisets if needed, we can assume that $\sigma(C) \le \frac{S}{3} \le \sigma(B)$. Since obviously $\frac{\sigma(B) + \sigma(C)}{2} = \frac{S}{3}$, we can use Lemma 1 with $\lambda = \frac{1}{2}$ to enforce all the conditions of the claim after at most $\lceil \frac{n}{2} \rceil$ swaps between elements of $B$ and $C$. We can, and shall assume from now on, that none of $\sigma(A), \sigma(B)$ and $\sigma(C)$ is equal to $\frac{S}{3}$. Renaming the multisets if needed, we can assume that, either (1) $\sigma(C) < \frac{S}{3} < \sigma(B) \le \sigma(A)$ or (2) $\sigma(C) \le \sigma(B) < \frac{S}{3} < \sigma(A)$. Let us address (1) first. By Lemma 2 and its proof, we have $\frac{\frac{S}{3} - \sigma(C)}{\sigma(B) - \frac{S}{3}} \ge 2$ so that $\lambda := \frac{\sigma(B) - \frac{S}{3}}{\sigma(B) - \sigma(C)} \le \frac{1}{3}$. We apply Lemma 1 to $B, C$ and the previous value of $\lambda$, turning $B$ into a multiset $B'$ such that $\vert \sigma(B') - \frac{S}{3} \vert \le \frac{1}{2}$ by means of at most $\lceil \frac{n}{3} \rceil$ swaps between the elements of $B$ and $C$. After applying those swaps, the multiset $C$ has been turned into a multiset $C'$ satisfying $\left\vert \frac{\sigma(A) + \sigma(C')}{2} - \frac{S}{3} \right\vert \le \frac{1}{4}$. We conclude this case by applying Lemma 1 to $A$ and $C'$ with $\lambda = \frac{1}{2}$. Let us now address (2). By Lemma 2 and its proof, we have $\frac{\sigma(A) - \frac{S}{3}}{\frac{S}{3} - \sigma(B)} \ge 2$ so that $\lambda : = \frac{\frac{S}{3} - \sigma(B)}{\sigma(A) - \sigma(B)} \le \frac{1}{3}$. We apply Lemma 1 to $A, B$ and the previous value of $\lambda$, turning $B$ into a multiset $B'$ such that $\vert \sigma(B') - \frac{S}{3} \vert \le \frac{1}{2}$ by means of at most $\lceil \frac{n}{3} \rceil$ swaps between the elements of $A$ and $B$. After applying those swaps, the multiset $A$ has been turned into a multiset $A'$ satisfying $\left\vert \frac{\sigma(A') + \sigma(C)}{2} - \frac{S}{3} \right\vert \le \frac{1}{4}$. We conclude this case by means of an application of Lemma 1 to $A'$ and $C$ with $\lambda = \frac{1}{2}$.

Luc Guyot
  • 7.9k
  • 2
  • 30
  • 51