Đị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^*$)
Trong $2n-1$ số luôn tồn tại $n$ số có tổng chia hết cho $n$
#1
Đã gửi 03-07-2015 - 09:00
#2
Đã gửi 21-10-2015 - 21:03
Đị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
- Zaraki, phatthemkem, Belphegor Varia và 3 người khác yêu thích
Đừng khóc vì chuyện đã kết thúc hãy cười vì chuyện đã xảy ra
Thật kì lạ anh không thể nhớ đến tên mình mà chỉ nhớ đến tên em
Chúa tạo ra vũ trụ của con người còn em tạo ra vũ trụ của anh
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh