Skip to main content
4 of 4
added 170 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 (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$.

Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459