Skip to main content
2 of 4
added 492 characters in body
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

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. 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 either $a_1+b_2+c_2$ or $a_2+b_1+c_2$ works, let it be the former, and either $b_1+c_2+a_2$ and $c_1+b_2+a_2$ works.

Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459