Chủ đề này có 1 trả lời

[thinhrost1]

Một trường hợp của định lý EGZ (Erdős Pál, Abraham Ginzburg és Abraham Ziv):

 

Cho p là một số nguyên tố. Chứng minh rằng từ 2p-1 số nguyên cho trước, luôn chọn được p số sao cho tổng của chúng chia hết cho p.

 

Các bạn cho mình xin cách giải sơ cấp với nhiều tài liệu viết rối quá

[viet nam in my heart]

Chứng minh cái này đã có trên diễn đàn rồi mà. Bài toán này đúng với mọi số $p$ không nhất thiết nguyên tố. Nhưng dễ thấy ta quy về chứng minh bài  toán trong trường hợp $p$ nguyên tố. Trong 1 bài viết của thầy Dũng trên báo THTT đã viết về định lý này. 

 

Định lý Erdos: Chứng minh rằng mọi tập hợp $2n-1$ phần tử luôn tồn tại $n$ phần tử có tổng chia hết cho $n$ ($n \in N^*$)

 

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

 

trong các số $s_1,s_2,...,s_p$ sẽ có $k\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

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)$

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

 

 

p/s: Hầu hết mọi tài liệu đều viết theo cách này. Cách này cũng sơ cấp mà có dùng gì cao cấp đâu 

Bài viết đã được chỉnh sửa nội dung bởi viet nam in my heart: 06-06-2016 - 20:17