Định lý EGZ

Định lý Erdős Pál, Abraham Ginzburg és Abraham Ziv:

Từ 2n-1 số nguyên cho trước, luôn chọn được n số sao cho tổng của chúng chia hết cho n.

Lời giải:

gọi định lý trên là mệnh đề $\mathcal{E}(n)$

$\blacksquare$ ta chứng minh $\mathcal{E}(p)$ đúng với $p\in \mathbb{P}$

Với $p=2$ thì dễ thấy đúng ta xét với $p$ lẻ

gọi các số trong tập là $a_1,a_2,...,a_{2p-1}$

giả sử không tồn tại $p$ số nào chia hết cho $p$

$\Rightarrow \left ( a_{i_1}+a_{i_2}+...+a_{i_p} \right )^{p-1}\equiv 1(mod\ p)$

$\Rightarrow \sum_{1\le i_1<...<i_p\le 2p-1}\left ( a_{i_1}+a_{i_2}+...+a_{i_p} \right )^{p-1}\equiv \begin{pmatrix} 2p-1\\p \end{pmatrix}(mod\ p)$ $(*)$
ta có
$\begin{pmatrix} 2p-1\\p \end{pmatrix}\equiv \begin{pmatrix} 1\\1 \end{pmatrix}\begin{pmatrix} p-1\\ 0 \end{pmatrix}\not \equiv 0(mod\ p)$
ta sẽ chứng minh vế trái $(*)$ chia hết cho $p$,thật vậy ta có
$\sum_{1\le i_1<...<i_p\le 2p-1}\left ( a_{i_1}+a_{i_2}+...+a_{i_p} \right )^{p-1}=\sum_{s_1+s_2+...+s_p=p-1}\frac{(p-1)!}{s_1!s_2!...s_p!}\sum _{1\le i_1<...<i_p\le 2p-1}a_{i_1}^{s_1}a_{i_2}^{s_2}...a_{i_p}^{s_p}$ (thức ra từ chỉ cần $\sum _{1\le i_1<...<i_p\le 2p-1}a_{i_1}^{s_1}a_{i_2}^{s_2}...a_{i_p}^{s_p}$)
trong các số $s_1,s_2,...,s_p$ sẽ có $m \in \left [ 1,p-1 \right ]$ số bằng $0$ nên sẽ có $\begin{pmatrix} 2p-1-(p-m)\\m \end{pmatrix}=\begin{pmatrix} p+m-1\\ m \end{pmatrix}$ cách chọn các số $a_{i_j}$
mà $s_j=0$ do đó số $a_{i_1}^{s_1}a_{i_2}^{s_2}...a_{i_p}^{s_p}$ sẽ được lặp $\begin{pmatrix} p+m-1\\m \end{pmatrix}$ lần ( Có ý nghĩa: sau khi loại bỏ $p-m$ số có số mũ khác 0 thì cần m số (trong $2p-1-(p-m)$ số) có mũ bằng $0$ (vì $a_i^0..a_n^0=1$))

mặt khác

$\begin{pmatrix} p+m-1\\ m \end{pmatrix}\equiv \begin{pmatrix} 1\\0 \end{pmatrix}\begin{pmatrix} m-1\\m \end{pmatrix}\equiv 0(mod\ p)$ (hoặc có thể dùng định nghĩa nhị thức newton để chứng minh.)

$\Rightarrow p\mid VT_{(*)}$

điều này dẫn đến mâu thuẫn

$\blacksquare$ ta chứng minh nếu $\mathcal{E}(u)$ và $\mathcal{E}(v)$ đúng thì $\mathcal{E}(uv)$ đúng

gọi $2uv-1$ số nguyên dương là $a_1,a_2,...,a_{2uv-1}$

vì $2uv-1>2u-1$ nên tồn tại $u$ số có tổng chia hết cho $u$ và gọi tổng đó là $b_1$

lặp lại $2v-2$ lần ta có các tổng $b_1,b_2,...,b_{2v-2}$ chia hết cho $u$

do đó còn lại $2uv-1-u(2v-2)=2u-1$ số thì chọn được tổng $b_{2v-1}$ số chia hết cho $u$

mặt khác trong các số $b_1,b_2,...,b_{2v-1}$ ta sẽ chọn được $v$ số chia hết cho $v$

mặt khác $v$ số này cũng chia hết cho $u$ nên $uv$ số này $($ do mỗi tổng có $u$ số $)$ chia hết cho $uv$

vậy bài toán được chứng minh hoàn toán