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 answered on the math.SE question - I think Harper's vertex isoperimetric inequality does the job. $\endgroup$ – Dap Apr 12 at 14:10

Your Answer

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

Browse other questions tagged or ask your own question.