Minimum number of balanced partitions

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.

Solution 1:

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