Định lý Erdös-Ginzburg-Ziv

Bài viết này nhắm giới thiệu tóm lược một định lý tương đối nổi tiếng trong lý thuyết số tổ hợp: Định lý Erdös-Ginzburg-Ziv. Nhiều người còn cho rằng định lý này là một trong những kết quả nền tàng để sinh ra ngành này.

Định lý được phát biểu như sau:

Định lý Erdös-Ginzburg-Ziv: Với mọi dãy gồm $2n-1$ số tự nhiên bất kỳ, tồn tại một dãy con gồm $n$ số hạng sao scho tổng của chúng là một bội của $n$. 

Định lý có khá nhiều cách chứng minh từ sơ cấp - có thể chứng minh được thông qua một loạt các bổ đề và có thể hiểu được chỉ với một chút kiến thức số học ở bậc phổ thông - đến cao cấp - chẳng hạn như sử dụng định lý Chevalley-Warning. Bài viết này giới thiệu hai cách chứng minh thường gặp nhất, với tham khảo từ tài liệu [1]. Bạn đọc quan tâm đến các chứng minh khác có thể xem tài liệu [2].

Để cho gọn, ta kí hiệu định lý Erdös-Ginzburg-Ziv cho $n$ bởi $EGZ(n)$. Đầu tiên ta sẽ chứng minh một kết quả đơn giản trước.

Bổ đề : Nếu $EGZ(m)$ đúng và $EGZ(n)$ đúng thì $EGZ(mn)$ cũng đúng.

Chứng minh: Ta cần chứng minh rằng trong bộ $2mn-1$ số nguyên dương bất kỳ, tồn tại $mn$ số có tổng chia hết cho $mn$. Để ý rằng $2mn-1 > 2m-1$, nên ta chọn được $m$ số nguyên dương có tổng chia hết cho $m$, ta loại đi $m$ số này thì còn $2mn-1-m=(2n-1)m-1$ số. Tiếp tục lặp lại như vậy, ta dễ thấy ngay rằng thuật toán phải dừng lại sau đúng $2n-1$ bước (vì khi đó chỉ còn $2mn-1-m(2n-1)=m-1<m$), tức là ta có một dãy tổng gồm $2n-1$ số, toàn bộ các số đều là bội của $n$. Mặc khác, theo $EGZ(n)$, tồn tại $n$ tổng sao cho tổng của $n$ tổng con này là một bội của $n$. Do mỗi tổng có đúng $m$ số, nên $n$ tổng của $mn$ số. $\blacksquare$.

Áp dụng định lý cơ bản của số học, ta suy ra ngay ta chỉ cần chứng minh $EGZ(p)$ đúng, trong đó $p$ là một số nguyên tố bất kì là đủ. Bây giờ ta sẽ chứng minh định lý Erdös-Ginzburg-Ziv cho một số nguyên tố $p$.

Chứng minh: Ta kí hiệu $2p-1$ số nguyên dương là $\left\lbrace a_i \right\rbrace_{i=1}^{2p-1}$ và không giảm tổng quát, ta có thể giả sử $a_i \le a_j$ nếu $i<j$. Nếu tồn tại một số nguyên $i$ sao cho $a_i = a_{i+p-1}$ thì theo quy ước ở trên, ta phải có $a_i = a_{i+1} = \ldots = a_{i+p-1}$. Vậy tổng $p$ số hiển nhiên là một bội của $p$ - bài toán được chứng minh xong. Như vậy ta chỉ cần xét trường hợp không tồn tại chỉ số $i$ thỏa $a_i = a_{i+p-1}$. 

Để chứng minh $EGZ(p)$ ta chứng minh kết quả mạnh hơn như sau: với mọi số nguyên dương $s$, tồn tại một dãy gồm $p$ số hạng sao cho tổng của chúng đồng dư với $s \pmod p$. Thật vậy, ta phân hoạch dãy gồm $2p-1$ số đã cho thành $p$ tập $A_i = \left\lbrace a_i, a_{i+p-1}\right\rbrace$ trong đó $i = \overline{1,p-1}$ và $A_{p}= \left\lbrace a_{2p-1}\right\rbrace$. Lấy modulo $p$, ta có thể xem các tập $A_i$ là tập con của $\mathbb{Z}_p$. Khi đó mệnh đề đã phát biểu ở trên tương đương với 

\[A_1+A_2+\ldots+A_{p} = \mathbb{Z}_p\]

Ta thấy rằng, chỉ cần chứng minh được vế trái có $p+1$ phần tử là đủ. Ta dự đoán rằng tổng $B_i = A_1+\ldots+A_i$ sẽ có $i+1$ phần tử. Thật vậy, giả sử ngược lại, ta suy ra phải tồn tại một chỉ số $i$ sao cho $B_i$ và $B_{i+1}$ có cùng số phần tử, điều này có nghĩa là 

\[C =B_i+a_{i+1} = B_i+a_{i+p}=D\]

Điều này kéo theo rằng $C+e=D$, với $e= a_{i+1}-a_{i+p}$, tức là nếu $x \in C$, thì $x+ke \in C$ với $k$ nguyên dương tùy ý. Do $p$ nguyên tố và $e$ không phải là một bội của $p$, ta phải có $\left\lbrace x, x+e, \ldots, x+(p-1)\ e\right\rbrace$ là một hệ thặng dư đầy đủ modulo $p$, nhưng điều này chỉ xảy ra khi $C=\mathbb{Z}_p$. Vậy ta hoàn tất chứng minh. $\blacksquare$