15
$\begingroup$

For any multiset $x_1,x_2,\ldots,x_{2n}$ of positive real numbers, a partition into two nonempty subsets $(A,B)$ is called "balanced" if $\text{sum}(A)\geq\text{sum}(B)-\max(B)$ and $\text{sum}(B)\geq\text{sum}(A)-\max(A)$.

What is the minimum number of balanced partitions, in terms of $n$?

For the case that all numbers are equal, a partition is balanced if and only if it puts $n$ numbers in each part. So there are $\binom{2n}{n}$ balanced partitions. I conjecture that this is also the minimum. The reason is that if the numbers are not equal, there is more "advantage" to be gained by subtracting the max, which should give more balanced partitions.

$\endgroup$
  • 1
    $\begingroup$ If all numbers are equal, shouldn't it result in just one partition? $\endgroup$ – Barbosa Sep 17 '18 at 16:28
  • 2
    $\begingroup$ @Barbosa The partitions are considered distinct if the labels are distinct. So $(\{x_1,x_2\},\{x_3,x_4\})$ and $(\{x_1,x_3\},\{x_2,x_4\})$ are distinct partitions, even if all the numbers are equal. $\endgroup$ – Karo Sep 17 '18 at 16:45
  • $\begingroup$ Do you require that the partition have half the members in $A$ and half in $B$, or is it just the sums that have to (almost) match? $\endgroup$ – Ross Millikan Sep 25 '18 at 22:44
  • 1
    $\begingroup$ Not sure this is a useful observation: "if the numbers are not equal, there is more 'advantage' to be gained by subtracting the max" is NOT true if the number of numbers is odd. (I know the OP has $2n$ numbers, which is why my observation may be useless.) E.g. for $\{1,1,1\}$, there are 6 balanced partitions: $A$ can be any of 3 singletons or any of 3 pairs. But for $\{1,10,100\}$, the $100$ can be in $A$ or $B$ (2 ways), which forces $10$ to be in the other set, and finally $1$ can be in either set (2 ways), for a total of 4 balanced partitions. Evenness somehow is important here... $\endgroup$ – antkam Sep 27 '18 at 21:32
  • 1
    $\begingroup$ @RossMillikan - if we require $|A|=|B|=n$, the conjecture is false. E.g. for $\{1,2,1001,1002\}$, the $1002$ can be in $A$ or $B$ (2 ways) which forces $1001$ to be in the other set. If we further restrict $|A|=|B|=2$ then $1$ and $2$ must also be in different sets. This gives only 4 balanced partitions where $|A|=|B|=2$, which is fewer than ${4 \choose 2} = 6$. However if there are no restrictions on $|A|, |B|$, this allows $1, 2$ to be together or separate, giving 8 balanced partitions. $\endgroup$ – antkam Sep 27 '18 at 21:41
1
$\begingroup$

$\binom{2n}{n}$ is optimal. This follows from a form of Harper's vertex isoperimetric inequality on the hypercube.

I'll use $n$ to be your $2n$ from now on. Let $n\geq 2$ and take any positive reals $x_1,\dots,x_n.$ Let $Q_n$ be the hypercube $\{0,1\}^n.$ Define

$$\mathcal A=\Big\{z\in Q_n: |z|>0\text{ and }\sum_{i\in z}x_i-\max_{i\in z}x_i> \sum_{i\not\in z}x_i\Big\}$$ $$\mathcal B=\{\{1,\dots,n\}\setminus z\mid z\in \mathcal A\}$$

Elements of $Q_n\setminus (\mathcal A\cup \mathcal B)$ correspond bijectively to balanced partitions.

I claim that the Hamming distance of any element of $\mathcal A$ from any element of $\mathcal B$ is at least $2.$ Suppose $z\in\mathcal B$ for some $j\not\in z.$ (This is the only case to check because $\mathcal A$ is upwards-closed and $\mathcal B$ is downwards-closed.) Then $$ \sum_{i\not\in (z\cup j)} x_i = \sum_{i\not\in z} x_i -x_j\geq \sum_{i\not\in z} x_i - \max_{i\not\in z} x_i > \sum_{i\in z}x_i \geq \sum_{i\in (z\cup \{j\})}x_i - \max_{i\in(z\cup \{j\})}x_j $$ which implies $z\cup\{j\}\not\in\mathcal A$ as required.

https://cseweb.ucsd.edu/~ccalabro/essays/harper.pdf, or B. Bollobás, Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability Chapter 16 Theorem 3, says:

There is a Hamming ball $\mathcal A_0$ with center $\{1,\dots,n\}$ and a Hamming ball $\mathcal B_0$ with center $\emptyset$ such that $|\mathcal A_0| =|\mathcal A|,$ and $|\mathcal B_0| = |\mathcal B|,$ and $d(\mathcal A_0, \mathcal B_0) \geq d(\mathcal A, \mathcal B).$

See those references for the definition of "a Hamming ball" and $d.$ In our case we get $d(\mathcal A_0, \mathcal B_0) \geq 2.$ I'll use Calabro's notation.

$n$ is assumed to be even. There is a unique $r$ such that $B_{r-1}(\{1,\dots,n\})\subsetneq \mathcal A_0\subseteq B_r(\{1,\dots,n\}).$ By symmetry, $B_{r-1}(\emptyset)\subsetneq \mathcal B_0\subseteq B_r(\emptyset)$ with the same $r.$ If $r\geq n/2$ then $\mathcal A_0$ contains a set of order $n/2,$ and $B_0$ contains all sets of order $n/2-1.$ So $d(\mathcal A_0,\mathcal B_0)\leq 1,$ a contradiction. If $r<n/2$ then all sets of order $n/2$ lie in $Q_n\setminus (\mathcal A_0\cup \mathcal B_0),$ so there are at least $\binom{n}{n/2}$ balanced partitions as required.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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