7
$\begingroup$

Given is a multiset $A$ of positive real numbers that can be partitioned into three subsets of equal sum (call this sum $s$). Is it true that more than $3/4$ of $A$'s subsets necessarily have sum at least $s$?

The bound $3/4$ certainly can't be increased: if $A$ consists of $1, 1, 1/k, 1/k, \dots, 1/k$, where $1/k$ appears $k$ times for some large $k$, then $s=1$ and the fraction of subsets with sum $\ge s$ approaches $3/4$.

It feels like this should follow from a known combinatorial result or technique, but I can't identify which one.

$\endgroup$
3
  • $\begingroup$ It might be worthwhile to take each element independently with probability $\frac12$ and look at the sum of those variables. Chebyshev's inequality is too weak to yield anything useful, but a Chernoff bound might be useful, I don't have time to try right now. $\endgroup$ Commented Dec 27, 2023 at 8:29
  • $\begingroup$ A stronger form of the Paley–Zygmund inequality, for example, shows that at least $\frac{4}{13}$ of the subsets have sum of at least $s$. $\endgroup$ Commented Dec 27, 2023 at 8:38
  • $\begingroup$ Using the fact that it can be partitioned I can improve this to $\frac47$ $\endgroup$ Commented Dec 27, 2023 at 8:47

1 Answer 1

10
$\begingroup$

Denote these subsets which sum up to $s$ by $\alpha, \beta, \gamma$. Partition each subset $\alpha, \beta, \gamma$ onto two disjoint parts: $\alpha=\alpha_1\sqcup \alpha_2$,$\beta=\beta_1\sqcup \beta_2$, $\gamma=\gamma_1\sqcup \gamma_2$ (some of these 6 parts may be empty). There exist $2^{|A|-3}$ such partitions. I claim that at least 6 out of 8 combined sets $\alpha_i\sqcup \beta_j\sqcup \gamma_k$ have sum at least $s$. Then totally we get at least $6\cdot 2^{|A|-3}=\frac34\cdot 2^{|A|}$ subsets, as needed (well, almost what is needed: we need a strict inequality. But there exist a partition for which 7 combined sets work, not 6: take $\alpha_1=\beta_1=\gamma_1=\emptyset$.) Denote by $a_1,a_2,b_1,b_2,c_1,c_2$ the sums of $\alpha_1,\alpha_2,\beta_1,\beta_2,\gamma_1,\gamma_2$ respectively. Then $a_1+a_2=b_1+b_2=c_1+c_2=s$.

If, say, the parts $a_1,b_1,c_1$ are large (i.e. at least $s/2$), then any combination with at least two large parts work (already 4 good combinations); also at least two out of three combinations with 1 large part (i.e. $a_1+b_2+c_2$, $a_2+b_1+c_2$, $a_2+b_2+c_1$) work, since the sum of any two of them is not less than $2s$.

$\endgroup$
2
  • $\begingroup$ I don't understand this answer. Are you saying the statement is wrong? Could you give a concrete example with numbers? Note that you don't have to take one number from each partition, you can take any subset. $\endgroup$ Commented Dec 27, 2023 at 8:57
  • $\begingroup$ I say that it is correct. There are $2^{n-3}$ partitions of the three our submultisets onto pairs ($n$ is the total number of elements), each corresponds to at least 6 combinations with total sum at least $s$. $\endgroup$ Commented Dec 27, 2023 at 9:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .