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

The question received no answer on Math.SE after four months.

  • $\begingroup$ I suspect the minimum occurs when all the x's are the same. Then the answer is 2n choose n, which is likely the best as for many multisets one can have many partitions of differing sizes. Gerhard "Halfway Towards Having A Proof" Paseman, 2019.01.28. $\endgroup$ – Gerhard Paseman Jan 29 at 6:20
  • 1
    $\begingroup$ What it is the origin and background of this question? $\endgroup$ – Fedor Petrov Jan 30 at 7:05
  • $\begingroup$ I asked a question on math.SE that I believe would lead to a decent lower bound for this problem (at least $\tfrac12\binom{n}{n/2}$ I think): Reverse Littlewood-Offord problem $\endgroup$ – Dap Jan 30 at 8:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.