Skip to main content
5 of 7
Adds a (disappointing) corrigendum for the claim and a seemingly more interesting proposition whose proof follows OP's suggestion
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" 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.

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