5
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ In your last paragraph, you have sketched an approach leading to the upper bound of $\frac{3}{2}n$ swaps. Following this approach, I obtain the upper bound of $\frac{23}{12}n$ swaps (see updated answer). You certainly have a much clever way of choosing of swaps. Would you be kind enough to share some insight? $\endgroup$
    – Luc Guyot
    Dec 17, 2023 at 23:46
  • 1
    $\begingroup$ @LucGuyot sorry I have no actual proof, I thought to have one but it wasn't that simple. I still suppose (but it is just a conjecture) that the actual bound might be lower than about $2n$. I have started a related question at math.stackexchange regarding the "ordered arrangement". $\endgroup$ Dec 18, 2023 at 11:26
  • $\begingroup$ I have reformulated the minimum number of swaps for the "ordered arrangement" into this question and removed the previous one. $\endgroup$ Dec 19, 2023 at 19:06
  • $\begingroup$ In relation with this question and your arrangement approach, I would have asked: "Consider $m$ sets with $n$ balls. Each set contains balls of the same colour and two distinct sets have distinct colours. Fill $m$ bins of size $n$ with the $mn$ coloured balls. What is the minimum number of swaps that render all bins monochrome? (we look for a number that is valid for every possible filling)." $\endgroup$
    – Luc Guyot
    Dec 19, 2023 at 21:42

2 Answers 2

4
$\begingroup$

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$

$\endgroup$
8
  • $\begingroup$ Wonderfully slick and simple! Checking my understanding: the integer $\ell_1$ is the $(n_1 + 1)$-th element of $X_1$ sorted in ascending order, but not necessarily the minimum of $Y_1$, right? (similar question for $m_4$). $\endgroup$
    – Luc Guyot
    Dec 18, 2023 at 9:15
  • 1
    $\begingroup$ Thanks! Regarding your question, $\ell_1$ is the minimum of $Y_1$ but the $(n_1+1)$th smallest element of $X_1$ is a candidate for $\ell_1$, so the inequalities become even better if $\ell_1$ is not the $(n_1+1)$th smallest element of $X_1$. $\endgroup$
    – Tony Huynh
    Dec 18, 2023 at 10:48
  • $\begingroup$ Thanks, got it! $\endgroup$
    – Luc Guyot
    Dec 18, 2023 at 11:39
  • 1
    $\begingroup$ I added more details. Please let me know if it is clear. I think I can also prove the full theorem (without any special assumptions). I will write it up here when I have time. $\endgroup$
    – Tony Huynh
    Dec 18, 2023 at 14:44
  • 1
    $\begingroup$ I think the situation you describe is impossible since the fourth set always has sum at least $S/4$ while the first two always each have sum at most $S/4$. Thus, the largest element from the fourth set will always be at least as large as the smallest element from one of the first two sets. Also, I think we might not be done without performing the last swap. For example, $d_1=d_2=d_3=-0.33$ and $d_4=0.99$ is possible (in the first case). Feel free to send me an email if it is still unclear (my email can be easily found online). $\endgroup$
    – Tony Huynh
    Dec 18, 2023 at 15:38
1
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Thank you. It's not clear to me why the second order finite difference is non-negative. Also, shouldn't we check also $\sigma(B')$ together with $\sigma(A')$? $\endgroup$ Dec 15, 2023 at 10:51
  • 1
    $\begingroup$ The 2nd order finite difference of $(s_i)$ is: $m_{i + 1} - m_i - (M_{i + 1} - M_i)$. For $\lambda = 1/2$, you get simultaneous approximation of the mean sum. But I felt that using smaller values of $\lambda$ could be useful when applying the lemma iteratively. I'll try to examplify this by proving the $3n/2$ bound. $\endgroup$
    – Luc Guyot
    Dec 15, 2023 at 11:21
  • 1
    $\begingroup$ @FabiusWiesner I have tried to illustrate how Lemma 1 (for values of $\lambda < \frac{1}{2}$) could be useful with the computation of an upper bound for the number of swaps in the case of three multisets. $\endgroup$
    – Luc Guyot
    Dec 16, 2023 at 14:35
  • 1
    $\begingroup$ Thank you for the effort and the detailed work. $\endgroup$ Dec 16, 2023 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.