Školjka

%V0 Uzmimo random skup $B$ i označimo $X$ = $|A+B|$. Definirajmo $t_i=1$ ako $i \in A+B$ i $t_i=0$ inače. Tada je $X=\sum{t_i}$, gdje je suma po svim ostacima modulo $n^2$. Po linearnosti očekivanja vrijedi: $E[X]=\sum{E[t_i]}=\sum{0 \cdot P[i \notin A+B]+1 \cdot P[i \in A+B]} = \sum{P[i \in A+B]}$ $P[i \in A+B] = P[\exists b \in B, i-b \in A]$ $1-P[i \in A+B] = P[\forall b \in B, i-b \notin A]$ Gornju vrijednost je lako izračunati; vrijednost $i-b$ mora izbjegavati onih $n$ ostataka u $A$ pa za to ima $\binom{n^2-n}{n}$ načina, a u nazivniku su svi mogući skupovi $B$. $P[\forall b \in B, i-b \notin A] = \frac{\binom{n^2-n}{n}}{\binom{n^2}{n}}$ $\frac{\binom{n^2-n}{n}}{\binom{n^2}{n}} = \frac{(n^2-2n-1)...(n^2-n)}{(n^2-n+1)..(n^2)} = \prod_{k=0}^{n-1}\frac{n^2-n-k}{n^2-k} =$ $= \prod_{k=0}^{n-1}(1-\frac{n}{n^2-k}) \le \prod_{k=0}^{n-1}(1-\frac{1}{n}) = (1-\frac{1}{n})^n \le \frac{1}{e}$ Sada slijedi: $E[X] = \sum P[i \in A+B] \ge n^2(1-\frac{1}{e}) > \frac{n^2}{2}$ Sada znamo da postoji $X \ge E[X] > \frac{n^2}{2}$, pa postoji $B$ s traženim svojstvom. $\blacksquare$