Return to Answer

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 repeatly 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)$. We also assume that $\sigma(Y_3) \leq \frac{S}{4}$ (the other cases are similar). Thus, there exist $d_1 \geq d_2 \geq d_3$ such that $\sigma(Y_i)=\frac{S}{4}-d_i$ for $i \in [3]$ and $\sigma(Y_4)=\frac{S}{4}+d_1+d_2+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_1+d_2+d_3 < m_4-\ell_1$. Thus, after swapping $m_4$ with $\ell_1$, we are done. $\Box$

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$

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 $|\sigma(X_i)-\sigma(X_j)| \leq 1$ for all $i,j$.

Proof. By renaming, we may assume that $k=4$. We repeatly 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)$. We also assume that $\sigma(Y_3) \leq \frac{S}{4}$ (the other cases are similar). Thus, there exist $d_1 \geq d_2 \geq d_3$ such that $\sigma(Y_i)=\frac{S}{4}-d_i$ for $i \in [3]$ and $\sigma(Y_4)=\frac{S}{4}+d_1+d_2+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_1+d_2+d_3 < m_4-\ell_1$. Thus, after swapping $m_4$ with $\ell_1$, the sum of any two sets differ by at most $1$. $\Box$

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 repeatly 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)$. We also assume that $\sigma(Y_3) \leq \frac{S}{4}$ (the other cases are similar). Thus, there exist $d_1 \geq d_2 \geq d_3$ such that $\sigma(Y_i)=\frac{S}{4}-d_i$ for $i \in [3]$ and $\sigma(Y_4)=\frac{S}{4}+d_1+d_2+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_1+d_2+d_3 < m_4-\ell_1$. Thus, after swapping $m_4$ with $\ell_1$, we are done. $\Box$

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 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 $|\sigma(X_i)-\sigma(X_j)| \leq 1$ for all $i,j$.

Proof. By renaming, we may assume that $k=4$. We repeatly 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)$. We also assume that $\sigma(Y_3) \leq \frac{S}{4}$ (the other cases are similar). Thus, there exist $d_1 \geq d_2 \geq d_3$ such that $\sigma(Y_i)=\frac{S}{4}-d_i$ for $i \in [3]$ and $\sigma(Y_4)=\frac{S}{4}+d_1+d_2+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_1+d_2+d_3 < m_4-\ell_1$. Thus, after swapping $m_4$ with $\ell_1$, the sum of any two sets differ by at most $1$. $\Box$