Ein einfaches (?) Lustiges kombinatorisches Problem!

Lassen Sie uns und eine ganze Zahl t > 0 festlegen .$0<E<1$$t>0$

für jedes und für jeden Vektor ˉ c ∈ [ 0 , 1 ] n, so dass ∑ i ∈ [ n ] c i ≥ E × $n$$\bar{c} \in [0,1]^n$$\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 }$

Ich weiß nicht, ob die Aussage wahr oder falsch ist. Ich glaube es ist wahr.

Meine Intuition ergibt sich aus der Beobachtung, dass für die Vektoren (mit der gewünschten Eigenschaft über die Summe) A ˉ c = ( E × $\bar{c} \in \{0,1\}^n$ ; In diesem Fall können wir nur eine Teilmenge aus der Menge{i|auswählen ci=1}.$A_{\bar{c}}= \binom{ E \times n}{t}$$\{ i ~|~ c_i = 1 \}$

In den anderen Fällen können wir mit der Koordinate in { i | eine gute Teilmenge erstellen (st die Summe ist größer als ) c i > E }, aber vielleicht auch mit wenigen Koordinaten aus der Menge { i | c i ≤ E } wir könnten andere gute Mengen erstellen!$E \times t$$\{ i ~|~ c_i > E \}$$\{ i ~|~ c_i \leq E \}$

Also, beweise es oder finde den Fehler! Ich hoffe, dass es ein lustiges Spiel für dich sein könnte!

Motivation der Frage :

Angenommen, Sie haben eine Zufallsvariable , ein typisches Maß dafür, "wie viel Zufälligkeit" in X vorhanden ist, ist die Min-Entropie$X\in \{0,1\}^n$$X$

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

In einem intuitiven Sinne ist die Min-Entropie der schlimmste Fall der berühmten Shannon-Entropie (das ist der Durchschnittsfall ).

Wir sind daran interessiert, die Min-Entropie der Zufallsvariablen zu senken, wobei Y gleichmäßig über die Menge { y | verteilt ist ∑ i y i = t } .$(Z=X \wedge Y| Y)$$Y$$\{ y ~|~ \sum_i y_i = t\}$

Wenn wir Glück haben, können wir locker die Bits von fangen , die "gute Entropie" haben, und wenn H ∞ ( X ) ≥ E n, dann ist H ∞ ( Z | Y ) ≥ E $X$$H_{\infty}(X)\geq En$$H_{\infty}(Z|Y)\geq Et$

Wie groß ist die Wahrscheinlichkeit, dass wir Glück haben?

Das Problem ist gut untersucht und es gibt viel Literatur, siehe zum Beispiel Lemma A.3. in der leckagebeständigen Public-Key-Kryptographie im Bounded-Retrieval-Modell

Die Vermutung in der Post gilt nicht, aber die schwächere Vermutung (in Bezug auf den Boden), die in den Kommentaren erwähnt wird, gilt. In der Tat hält etwas Stärkeres.

---

Lemma 1. Die Vermutung in der Post gilt nicht. Das heißt, es gibt eine Instanz, die die gegebenen Annahmen erfüllt, wobei

$$\big|\textstyle\big\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \, t \big\}\big| < \binom{ E \, n}{ t }.$$

$n=3$$c=(1, 1, 0.7)$$E=2.7/3=0.9$$t=2$$E\, t = 1.8$

$$\big|\textstyle\{ S \subseteq [3] : \sum_{i \in S}~ c_i \geq 1.8 \}\big| = 2$$ $S$$\{1,1\}$$\{1,1,0.7\}$$\binom{ 2.7}{ 2 } = 2.7\cdot 1.7\,/\, 2 = 2.295>2. ~~~\Box$

---

$\lfloor E\, n \rfloor$

Lemma 2. $0<E<1$$n,t>0$$c \in [0,1]^n$$\sum_{i\in [n]} c_i \geq E\, n$

$$\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 }.$$

$a=\lfloor E\, n\rfloor$$a=E\,n$$E$$c_i$$\sum_i c_i \ge E\,n$$E\,t$$t\le a$

$S\subseteq [n]$$n-d$$d=a-\lceil a\,t/n\rceil \ge 0$$\sum_{i\in[n]} c_i \ge a$$S$$d$$\sum_{i\in S} c_i \ge a-d = \lceil a\,t/n\rceil = \lceil E\,t\rceil \ge E\,t$

$S$

${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}~~~$$n>a$

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

$a-d = \lceil a\,t/n\rceil \le t$$a/n = E < 1$$~~\Box$