|
|
|
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
| Ðiều Chỉnh | Xếp Bài |
14-11-2007, 02:06 PM | #1 |
+Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 1,250 Thanks: 119 Thanked 616 Times in 249 Posts | Một đồng dư modulo nguyên tố Một đồng dư modulo nguyên tố Người dịch: Nguyễn Trung TuânHao Pan Tặng Thầy nhân dịp 20-11-2007 Trong năm 1961, Erdos, Ginzburg, và Ziv [3] đã tìm ra định lý nổi tiếng sau đây, bây giờ nó là trung tâm của các bài toán $0- $ tổng( về các bài toán này các bạn có thể tìm trong [1],[2] và [5]). Định lý EGZ. Giả sử $n $ là một số nguyên dương. Khi đó với mỗi dãy $a_1,a_2,\cdots,a_{2n-1} $ gồm $2n-1 $ số nguyên có một dãy con $a_{i_1},a_{i_2},\cdots, a_{i_n} $ độ dài $n $ sao cho tổng $\sum_{j=1}^na_{i_j} $ chia hết cho $n $. Dễ kiểm tra thấy rằng định lý EGZ là nhân tính, nghĩa là, nếu mệnh đề đúng với $n=k $ và $n=l $ thì nó cũng đúng với $n=k\cdot l $. Do đó chỉ cần chứng minh định lý đúng với $n $ nguyên tố là đủ. Trong các chứng minh cổ điển của định lý, trường hợp $n $ nguyên tố thường có được từ định lý Cauchy-Davenport hoặc định lý Chevalley-Waring (xem [6]). Tuy nhiên, với sự giúp đỡ của định thức Vandermonde, Gao [4] cho một chứng minh khác của định lý EGZ dựa trên đồng dư sau $\sum_{I\subseteq\{1,\cdots,2p-1\},|I|=p}\;(\sum_{i\in I}a_i)^{p-1}\equiv 0\pmod{p},\; (*) $ở đó $p $ là một số nguyên tố và $a_1,\cdots,a_{2p-1} $ là các số nguyên bất kì. Chú ý rằng định lý EGZ là một hệ quả đơn giản của $(*) $ vì theo định lý Fermat nhỏ chúng ta có $\left|\{I\subseteq\{1,2,\cdots,2p-1\}:\sum_{i\in I}a_i\equiv 0\pmod{p},|I|=p\}\right|\equiv $ $\equiv\sum_{I\subseteq\{1,\cdots,2p-1\},|I|=p}\;(1-(\sum_{i\in I}a_i)^{p-1})\equiv C_{2p-1}^p\equiv 1\pmod{p}. $ Trong bài báo này, chúng tôi sẽ chứng minh định lý sau, mà đồng dư của Gao chỉ là một hệ quả đơn giản của nó: Định lý. Giả sử $p $ là một số nguyên tố và $k $ là một số nguyên dương thỏa mãn $k\leq p $. Cho $f(x_1,\cdots,x_k) $ là một đa thức đối xứng với hệ số nguyên biến $x_1,\cdots,x_k $. Nếu bậc của $f $ nhỏ hơn $k $ thì với một dãy bất kì gồm $p+k-1 $ số nguyên $a_1,a_2,\cdots,a_{p+k-1} $, chúng ta có $\sum_{1\leq i_1<\cdots<i_k\leq p+k-1}\; f(a_{i_1},\cdots,a_{i_k})\equiv f(0,\cdots,0)\pmod{p} $ nếu $k=p $ và $\equiv 0\pmod{p} $ trong trường hợp còn lại. Chứng minh. Chứng minh là sơ cấp, chỉ cần đến một tính chất số học cơ bản của hệ số nhị thức: $C_{p+k-1}^k\equiv 1\pmod{p} $ nếu $k=p $ và $\equiv 0\pmod{p} $ nếu $1\leq k<p $. Chúng tôi sẽ chứng minh định lý bằng quy nạp theo $k $. Khi $k=1 $, vì $\deg f<k $ nên $f $ phải là một hằng số $c $. Trong trường hợp này $\sum_{1\leq i\leq p}f(a_i)=p\cdot c\equiv 0\pmod{p} $. Bây giờ giả sử rằng $k>1 $ và định lý là đúng với tất cả các giá trị nhỏ hơn $k $. Đặt $S_{f,k}(x_1,\cdots,x_{p+k-1})=\sum_{1\leq i_1<\cdots<i_k\leq p+k-1}\; f(x_{i_1},\cdots,x_{i_k}) $ và viết $f(x_1,\cdots, x_k) $ dưới dạng $f(x_1,\cdots,x_k)=\sum_{j=0}^{k-1}g_j(x_1,\cdots,x_{k-1})x_k^j $, ở đây $g_j $ là các đa thức biến $x_1,\cdots,x_{k-1} $. Từ tính đối xứng của $f $ ta có $S_{f,k} $ và tất cả $g_j $ là các đa thức đối xứng. Tiếp theo chúng ta thấy rằng $S_{f,k}(a_1,\cdots,a_{p+k-1})=\sum_{1\leq i_1<\cdots<i_k\leq p+k-2}\;f(a_{i_1},\cdots,a_{i_k})+ $ $+\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\; f(a_{i_1},\cdots,a_{i_{k-1}},a_{p+k-1}) $. Do đó $S_{f,k}(a_1,\cdots,a_{p+k-1})-S_{f,k}(a_1,\cdots,a_{p+k-2} ,0) $ $=\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\;(f(a_{i_1},\cdots,a_{i_{k-1}},a_{p+k-1})-f(a_{i_1},\cdots,a_{i_{k-1}},0)) $ $=\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\;\left(\sum_{j=0}^{k-1}g_j(a_{i_1},\cdots,a_{i_{k-1}})a_{p+k-1}^j-g_0(a_{i_1},\cdots,a_{i_{k-1}})\right) $ $=\sum_{j=1}^{k-1}a_{p+k-1}^j\;\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\;g_j(a_{i_1},\cdots,a_{i_{k-1}}) $ $=\sum_{j=1}^{k-1}a_{p+k-1}^jS_{g_j,k-1}(a_1,\cdots,a_{p+k-2}) $. Vì $k\leq p $ và $\deg g_j\leq \deg f-j<k-j $, chúng ta có thể dùng giả thiết quy nạp để có $S_{g_j,k-1}(a_1,\cdots,a_{p+k-2})\equiv 0\pmod{p}\forall j=\overline{1,k-1} $. Do đó $S_{f,k}(a_1,\cdots,a_{p+k-1})\equiv S_{f,k}(a_1,\cdots,a_{p+k-2},0)\pmod{p} $. Từ đây, sử dụng tính đối xứng của $S_{f,k} $, chúng ta có $S_{f,k}(a_1,\cdots,a_{p+k-1})\equiv S_{f,k}(0,\cdots,0)\pmod{p} $. Cuối cùng, bởi định nghĩa của $S_{f,k} $, ta có $S_{f,k}(a_1,\cdots,a_{p+k-1})=C_{p+k-1}^kf(0,\cdots,0)\equiv f(0,\cdots,0)\pmod{p} $ nếu $k=p $ và $\equiv 0\pmod{p} $ nếu $1\leq k<p $. Định lý được chứng minh. Tài liệu tham khảo [1]N. Alon and M. Dubiner, Zero-sum sets of prescribed size, in: "Combinatorics, Paul Erdos is Eighty", Bolyai Society, Mathematical Studies, Keszthely, Hungary, 1993, 33-50. [2]Y. Caro, "Zero-sum problems: a survey" Discrete Math. , 152 (1996) pp. 93–113. [3]Erdos, P., Ginzburg, A., Ziv, A. Theorem in additive number Theory,. Bull. Res. Council, Israel, 10 F(1961) 41–43. [4]W. D. Gao - Two addition theorems on groups of prime order, J. Number Theory, Vol.56 (1996) 211-213. [5]W.D. Gao, A. Geroldinger, On zero sum sequences in Zn ⊕ Zn Integers 3 (A8) (2003) 45 (electronic). [6]M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, 1996. __________________ T. |
The Following 2 Users Say Thank You to n.t.tuan For This Useful Post: | phamtoan (04-09-2011), thaygiaocht (11-01-2014) |
14-11-2007, 10:59 PM | #2 |
B&S-D Tham gia ngày: Nov 2007 Bài gởi: 589 Thanks: 395 Thanked 147 Times in 65 Posts | |
16-11-2007, 05:59 PM | #3 |
+Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 21 Thanks: 0 Thanked 0 Times in 0 Posts | Mình không chứng minh được cái đó! Có ai biết cách c/m khác của EGZ nếu không dùng đồng dư của Gao không? |
17-11-2007, 01:05 PM | #4 |
+Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 289 Thanks: 85 Thanked 162 Times in 100 Posts | anh Tuân có ebook phần này không ,đưa lên diễn đàn,chứ thời gian đâu mà ngồi trước máy tính đọc cơ chứ __________________ Ultra |
17-11-2007, 11:23 PM | #5 |
+Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 1,250 Thanks: 119 Thanked 616 Times in 249 Posts | Quang chắc chịu không chứng minh được tính nhân tính rồi. Để anh giúp nhé! Trong $2kl-1 $ số nguyên, chọn $l $ số có tổng chia hết cho $l $(chọn được vì $2kl-1>2l-1 $),sau đó chọn $l $ số từ nhóm còn lại có tổng chia hết cho $l $, cứ làm như thế đến khi còn $l-1 $ số, chúng ta được $2k-1 $ nhóm, mỗi nhóm gồm $l $ số có tổng chia hết cho $l $, trong $2k-1 $ tổng này, ta chọn ra $k $ tổng có tổng chia hết cho $k $. Gom lại có đủ $kl $ số rồi đấy! __________________ T. |
17-11-2007, 11:37 PM | #6 |
+Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 16 Thanks: 0 Thanked 0 Times in 0 Posts | kl số đó sẽ thỏa mãn nếu gcd(k,l)=1, tuy nhiên trong chứng minh trên, thay vì chọn 2k-1 tổng, ta chọn 2k-1 số là trung bình cộng của các tổng đó là xong. |
17-11-2007, 11:42 PM | #7 |
+Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 1,250 Thanks: 119 Thanked 616 Times in 249 Posts | Cảm ơn Tom, đây là một chứng minh khác của EGZ. Nguồn: Mathlinks.ro Người post: ZetaX [Only registered and activated users can see links. ] __________________ T. |
Bookmarks |
|
|