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

[Bui Ba Anh]

Đị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^*$)

[nhungvienkimcuong]

Đị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

Bài viết đã được chỉnh sửa nội dung bởi nhungvienkimcuong: 21-10-2015 - 21:15