A simple(?) funny combinatorial problem!

Question

Let we fix $0<E<1$ and an integer $t>0$.

for any $n$ and for any vector $\bar{c} \in [0,1]^n$ such that $\sum_{i\in [n]} c_i \geq E \times n$

$A_{\bar{c}} :=|\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \times t \}| \geq \binom{ E \times n}{ t }$

I don't know if the statament is true o false. I think it's true.

My intuition come from the observation that for the vectors $\bar{c} \in \{0,1\}^n$ (with the desidered property about the sum) we have $A_{\bar{c}}= \binom{ E \times n}{t}$; in this case we can only select subset from the set $\{ i ~|~ c_i = 1 \}$.

In the others case we can create good subset (s.t. the sum is greater then $E \times t$) using the coordinate in $\{ i ~|~ c_i > E \}$ but also, maybe, using few coordinate from the set $\{ i ~|~ c_i \leq E \}$ we could create other good set!

So,Prove it or find the bug! hoping that it could be a funny game for you!

Motivation of the question:

Suppose you have a random variable $X\in \{0,1\}^n$, a typical measure of "how much randomness" there is in $X$ is the min-entropy

$H_{\infty}(X) = min_{x} \{ -log(Pr[X = x]) \}$

In some intuitive sense the min-entropy is the worst case of the famous Shannon Entropy (that is the average case).

We are interested to lowerbound the min-entropy of the random variable $(Z=X \wedge Y| Y)$ where $Y$ is uniformely distributed over the set $\{ y ~|~ \sum_i y_i = t\}$.

Loosely speaking if we are lucky we can catch the bits of $X$ that have "good entropy" and so we if $H_{\infty}(X)\geq En$ then $H_{\infty}(Z|Y)\geq Et$

What is the probability that we are lucky?

The problem is well-studied one and there exists a lot of literature, for example see Lemma A.3. in Leakage-Resilient Public-Key Cryptography in the Bounded-Retrieval Model

Answer 1

The conjecture in the post does not hold, but the weaker conjecture (with respect to the floor) mentioned in the comments does hold. In fact, something stronger holds.

---

Lemma 1. The conjecture in the post does not hold. That is, there is an instance satisfying the given assumptions where $$\big|\textstyle\big\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \, t \big\}\big| < \binom{ E \, n}{ t }.$$

Proof. Consider the instance with $n=3$, $c=(1, 1, 0.7)$, $E=2.7/3=0.9$, and $t=2$. Then $E\, t = 1.8$. For the left-hand side, we have $$\big|\textstyle\{ S \subseteq [3] : \sum_{i \in S}~ c_i \geq 1.8 \}\big| = 2$$ because any subset $S$ that does not contain both 1's sums to at most 1.7, and there are only two subsets ($\{1,1\}$ and $\{1,1,0.7\}$) containing both 1's. And the right-hand side is $\binom{ 2.7}{ 2 } = 2.7\cdot 1.7\,/\, 2 = 2.295>2. ~~~\Box$

---

The weaker conjecture suggested in the comments, namely the bound w.r.t. the floor, $\lfloor E\, n \rfloor$, does hold. In fact something slightly stronger holds:

Lemma 2. Fix $0<E<1$, integers $n,t>0$, and vector $c \in [0,1]^n$ with $\sum_{i\in [n]} c_i \geq E\, n$.
Then $$\big|\textstyle\big\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E\, t \big\}\big| \,>\, \binom{ \lfloor E\, n\rfloor}{ t } + \binom{ \lfloor E\, n\rfloor}{ t+1 } + \cdots + \binom{ \lfloor E\, n\rfloor}{ \lfloor E\, n\rfloor }.$$

Proof. Let $a=\lfloor E\, n\rfloor$. Assume WLOG that $a=E\,n$. (Otherwise scale $E$ and each $c_i$ down by a uniform factor to make it so. This maintains $\sum_i c_i \ge E\,n$ and changes neither which subsets sum to at least $E\,t$ nor the desired lower bound on the number of such subsets.) Assume WLOG that $t\le a$ (otherwise the claim holds trivially).

Consider any subset $S\subseteq [n]$ of size at least $n-d$, where $d=a-\lceil a\,t/n\rceil \ge 0$. Since $\sum_{i\in[n]} c_i \ge a$ and $S$ contains all but at most $d$ elements (each of which is at most 1), we have $\sum_{i\in S} c_i \ge a-d = \lceil a\,t/n\rceil = \lceil E\,t\rceil \ge E\,t$, as desired.

The number of such subsets $S$ is

${n\choose n-d} + {n \choose n-d+1} + \cdots + {n \choose n-1} + {n \choose n}$

$ = {n\choose d} + {n \choose d-1} + \cdots + {n \choose 1} + {n \choose 0}$

$ > {a\choose d} + {a \choose d-1} + \cdots + {a \choose 1} + {a \choose 0}~~~$ (using $n>a$)

$ = {a\choose a-d} + {a \choose a-d+1} + \cdots + {a \choose a-1} + {a \choose a}.$

But $a-d = \lceil a\,t/n\rceil \le t$ (using $a/n = E < 1$), so the last sum is at least the desired lower bound on the number of good subsets. $~~\Box$