Skip to main content
4 of 7
Fixes a typo
Luc Guyot
  • 7.9k
  • 2
  • 30
  • 51

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

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