Točno
23. srpnja 2014. 13:16 (9 godine, 12 mjeseci)
Let
![A](/media/m/5/a/e/5ae81275ee67d638485e903bdc0e9cde.png)
be a set of
![N](/media/m/f/1/9/f19700f291b1f2255b011c11d686a4cd.png)
residues
![\pmod{N^{2}}](/media/m/c/4/b/c4b2401db2db4648e7055eadf1ee4744.png)
. Prove that there exists a set
![B](/media/m/c/e/e/ceebc05be717fa6aab8e71b02fe3e4e3.png)
of
![N](/media/m/f/1/9/f19700f291b1f2255b011c11d686a4cd.png)
residues
![\pmod{N^{2}}](/media/m/c/4/b/c4b2401db2db4648e7055eadf1ee4744.png)
such that
![A + B = \{a+b|a \in A, b \in B\}](/media/m/f/9/5/f95da7a7c29b44bb9cf325090bd53668.png)
contains at least half of all the residues
![\pmod{N^{2}}](/media/m/c/4/b/c4b2401db2db4648e7055eadf1ee4744.png)
.
%V0
Let $A$ be a set of $N$ residues $\pmod{N^{2}}$. Prove that there exists a set $B$ of $N$ residues $\pmod{N^{2}}$ such that $A + B = \{a+b|a \in A, b \in B\}$ contains at least half of all the residues $\pmod{N^{2}}$.
Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.
Uzmimo random skup
![B](/media/m/c/e/e/ceebc05be717fa6aab8e71b02fe3e4e3.png)
i označimo
![X](/media/m/9/2/8/92802f174fc4967315c2d8002c426164.png)
=
![|A+B|](/media/m/e/b/5/eb5308d3730e6e4d19e0ebd4f70660d4.png)
.
Definirajmo
![t_i=1](/media/m/7/f/e/7fe4d4ece9a86f7c4af06b5cfd58e612.png)
ako
![i \in A+B](/media/m/e/7/2/e72cda4d3126cba832760f820c0f278e.png)
i
![t_i=0](/media/m/3/0/3/303b635c07d511529a896883eafb135f.png)
inače. Tada je
![X=\sum{t_i}](/media/m/5/9/2/5920916ce88f5a3af09922475aaf63f1.png)
, gdje je suma po svim ostacima modulo
![n^2](/media/m/3/6/a/36a0dd5a7e7ff0e6bbc714e33ddb1d63.png)
.
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]}](/media/m/3/b/a/3bac472dc6074736d60eda603f76cd60.png)
![P[i \in A+B] = P[\exists b \in B, i-b \in A]](/media/m/e/7/9/e79dc340c3bf4919ad58bf699e0520bb.png)
![1-P[i \in A+B] = P[\forall b \in B, i-b \notin A]](/media/m/0/7/f/07fcc5b695bc3a4cd6038f2489d74e02.png)
Gornju vrijednost je lako izračunati; vrijednost
![i-b](/media/m/c/2/8/c28bb4571e54ee89dc6f18543e3aa968.png)
mora izbjegavati onih
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
ostataka u
![A](/media/m/5/a/e/5ae81275ee67d638485e903bdc0e9cde.png)
pa za to ima
![\binom{n^2-n}{n}](/media/m/d/c/f/dcf070660c875fc539fbf70ac4885edc.png)
načina, a u nazivniku su svi mogući skupovi
![B](/media/m/c/e/e/ceebc05be717fa6aab8e71b02fe3e4e3.png)
.
![P[\forall b \in B, i-b \notin A] = \frac{\binom{n^2-n}{n}}{\binom{n^2}{n}}](/media/m/f/e/3/fe3f766d7ca3f1d71b41438d6731f30d.png)
![\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} =](/media/m/9/f/3/9f34f4d55746a8d9416b4015ba0094ff.png)
![= \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}](/media/m/c/1/9/c19f0586705615e16bd82de904226259.png)
Sada slijedi:
![E[X] = \sum P[i \in A+B] \ge n^2(1-\frac{1}{e}) > \frac{n^2}{2}](/media/m/5/7/8/5787aa8007320ad39fef05b698d1ec22.png)
Sada znamo da postoji
![X \ge E[X] > \frac{n^2}{2}](/media/m/a/f/8/af861015507a418dfe4e69bbab5a300c.png)
, pa postoji
![B](/media/m/c/e/e/ceebc05be717fa6aab8e71b02fe3e4e3.png)
s traženim svojstvom.
%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$
16. kolovoza 2014. 15:08 | abeker | Točno |