Minimum number of swaps to make multisets elements sums close

Question

This problem was originally posted at math.stackexchange but there is no answer there, even after a (now expiring) bounty.

Choose $4$ multisets of size $n$ with elements $x \in \mathbb{R}$, $0 \le x \le 1$.

We want to swap elements between any two multisets repeatedly till the absolute difference between the sum of the elements of any multiset and the sum of the elements of any other multiset is not greater than $1$.

The worst case seems to be when two multisets are composed by all $1$ and the other two by all $0$, needing $n$ swaps.

For a generalization to $q$ multisets it seems that the worst case could be half multisets composed by all $1$ and the other half by all $0$, with $\frac{n\lfloor{q^2/4}\rfloor}{q}$ swaps.

Another observation (from here) is that if the sum of the elements of all multisets is $S$, and in the final valid configuration the minimum sum is $m$ then the sum of the elements of the other $3$ multisets must be less or equal than $3m+3$, therefore $4m+3 \ge S$, i.e. $m \ge (S-3)/4$, and similarly the maximum sum $M$ must satisfy $M \le (S+3)/4$.

I believe that we could arrange the elements in the four multisets $A = \{a_1, a_2, \ldots \},B = \{b_1, b_2, \ldots \},C = \{c_1, c_2, \ldots \},D = \{d_1, d_2, \ldots \}$ so that: $a_1 \le b_1 \le c_1 \le d_1 \le a_2 \le b_2 \le c_2 \le d_2 \le a_3 \le b_3 \le \ldots$, which guarantees the requirement, in at most $3n/2$ swaps, but this is more than the maximum conjectured value of $n$. [EDIT: I have no proof for the $3n/2$ bound, so it has no basis; I thought it were simpler.]

How can we prove that for any initial choice the number of needed swaps is at most $n$?

Answer 1

Here is a short proof that at most $2n-2$ swaps are necessary. We proceed by induction on $n$. For the base case $n=1$, it is clear that no swaps are necessary. For the inductive step, let $X_1,X_2,X_3,X_4$ be multisets of $n$ numbers in $[0,1]$, with $n \geq 2$. For each $i \in [4]$, arbitrarily choose $x_i \in X_i$, and let $Y_i=X_i \setminus \{x_i\}$. By induction, we may perform at most $2n-4$ swaps to $Y_1 ,\dots, Y_4$ to obtain $Y_1', \dots, Y_4'$ such that $|\sigma(Y_i') - \sigma(Y_j')| \leq 1$ for all $i,j$. By renaming, we may assume that $\sigma(Y_1') \leq \sigma(Y_2') \leq \sigma(Y_3') \leq \sigma(Y_4')$. It suffices to reorder $x_1, \dots, x_4$ using at most two swaps, such that $|\sigma(Y_i' \cup \{x_i)\}) - \sigma(Y_j' \cup \{x_j\})| \leq 1$ for all $i,j$.

By performing a single swap, we may assume that $x_1$ is the largest element among $x_1, \dots, x_4$. If we can perform an additional swap so that $x_1 \geq x_2 \geq x_3 \geq x_4$, then we are done since $\sigma(Y_1') \leq \sigma(Y_2') \leq \sigma(Y_3') \leq \sigma(Y_4')$. This is always possible unless $x_1 \geq x_3 \geq x_4 \geq x_2$, or $x_1 \geq x_4 \geq x_2 \geq x_3$. In the first case we choose the index $i \in \{3,4\}$ such that $\sigma(Y_i')+x_{i}$ is maximum and we swap $x_i$ with $x_2$. In the second case, we choose the index $i \in \{2,3\}$ such that $\sigma(Y_i')+x_{i}$ is minimum and we swap $x_i$ with $x_4$. $\Box$

By choosing $x_1, x_2, x_3, x_4$ more cleverly, it might be possible to improve the bound.

Here is a different proof that at most $n$ swaps are necessary when there is a unique multiset whose sum is at least the average sum. I think a similar proof can handle the general case.

Lemma. Let $X_1,X_2,X_3,X_4$ be multisets of $n$ numbers in $[0,1]$ with total sum $S$. If there is a unique index $k \in [4]$ such that $\sigma(X_k) \geq \frac{S}{4}$, then we can perform at most $n$ swaps so that the pairwise sums of the four resulting sets differ by at most $1$.

Proof. By renaming, we may assume that $k=4$. We repeatedly perform the following operation. Choose $i \in [3]$ such that $\sigma(X_i)$ is minimum. Swap the smallest element of $X_i$ with the largest element of $X_4$ provided that the sum of (the new) $X_4$ is still at least $\frac{S}{4}$. We claim that this operation can be performed at most $n-1$ times. Suppose not, and let $X_1', X_2', X_3', X_4'$ be the resulting sets after $n$ of these swaps. For each $i \in [3]$ let $n_i$ be the number of swaps involving the $i$th set. By assumption $\sigma(X_4') \geq \frac{S}{4}$. On the other hand, $$\sigma(X_4') \leq \frac{n_1}{n} \sigma(X_1) + \frac{n_2}{n} \sigma(X_2) + \frac{n_3}{n} \sigma(X_3) < \frac{n_1+n_2+n_3}{n} \frac{S}{4}=\frac{S}{4}, $$ which is a contradiction. Thus, let $m \leq n-1$ be the number of times these swaps are performed and let $Y_1, \dots, Y_4$ be the resulting sets after these $m$ swaps. By renaming, we may assume $\sigma(Y_1) \leq \sigma(Y_2) \leq \sigma(Y_3)$. For each $i \in [4]$ let $\sigma(Y_i)=\frac{S}{4}+d_i$.

First suppose $\sigma(Y_3) \leq \frac{S}{4}$. Thus, $d_1 \leq d_2 \leq d_3 \leq 0$ and $d_4=-(d_1+d_2+d_3) \geq 0$. Let $m_4$ be the maximum element of $Y_4$ and $\ell_1$ be the minimum element of $Y_1$. Since the operation cannot be performed $m+1$ times, we have $d_4 < m_4-\ell_1$. Thus, after swapping $m_4$ with $\ell_1$, we are done.

Next suppose $\sigma(Y_1) \leq \sigma(Y_2) \leq \frac{S}{4} \leq \sigma(Y_3)$. Thus, $d_1 \leq d_2 \leq 0$; $d_3 \geq 0$; and $d_4=-(d_1+d_2+d_3) \geq 0$. Let $Y_3'$ be the set obtained from $Y_3$ by reversing the last swap. Since our procedure always chooses the set with the smallest sum to perfrom a swap on, we conclude that $\sigma(Y_3') \leq \sigma(Y_1)$. Thus, $$\sigma(Y_3)-\sigma(Y_1) \leq \sigma(Y_3')+1-\sigma(Y_1) \leq 1$$.
Therefore, if $d_4 \leq d_3$, we are done. So, we may assume $d_4>d_3$. Let $m_4$ be the maximum element of $Y_4$ and $\ell_1$ be the minimum element of $Y_1$. Since the operation cannot be performed $m+1$ times, we have $d_4 < m_4-\ell_1$. Thus, after swapping $m_4$ with $\ell_1$, we are again done.

The last case $\sigma(Y_1) \leq \frac{S}{4} \leq \sigma(Y_2) \leq \sigma(Y_3)$ is similar and is omitted. $\Box$

Answer 2

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