Bổ đề Burnside và áp dụng của nó vào bài toán đếm


Cho X là một tập hợp và G là một nhóm. Ta nói G tác động trên X, hay X là một G-tập, nếu có hàm G\times X\to X, (g,x)\mapsto gx thoả mãn ex=x\forall x\in Xg_1(g_2x)=(g_1g_2)x\forall x\in X\forall g_1,g_2\in G, ở đây e là phần tử đơn vị của G.

Gìơ ta xét một G-tập X, với mỗi x\in X, ta gọi quỹ đạo của x là tập \{gx|g\in G\}. Các quỹ đạo khác nhau của các phần tử trong X làm thành một phân hoạch của X, thật vậy, quan hệ xRy nếu có g\in G để x=gy là một quan hệ tương đương trên X. Khi XG là các tập hữu hạn thì ta có thể tính số khối của phân hoạch này theo bổ đề sau đây.

Bổ đề Burnside. Nếu X là một G-tập hữu hạn (nghĩa là XG là các tập hữu hạn và X là một G-tập) và N là số các quỹ đạo khác nhau của các phần tử trong X thì N=\dfrac{1}{|G|}\sum_{g\in G}F(g), trong đó với mỗi g\in G, F(g) là số phần tử của tập \{x\in X|gx=x\}.

Tôi sẽ không đưa ra chứng minh nào của bổ đề này ở  đây, các bạn có thể tìm một chứng minh  trong sách Tổ hợp của Ngô Đắc Tân hay sách về lý thuyết nhóm của Rotman. Gìơ ta đi xét các áp dụng của bổ đề này vào giải các bài toán đếm, các bài tập này đều có trong sách của Rotman.

Bài 1. Cho nq là các số nguyên dương. Hỏi có bao nhiêu lá cờ gồm n mảnh sao cho mỗi mảnh mang một trong q màu cho trước?(Ví dụ một lá cờ như vậy là cờ của Pháp gồm 3 mảnh).

Lời giải. Vì khi ta tô màu một mặt của lá cờ thì mặt sau sẽ được xác định hoàn toàn màu. Nên số lá cờ bằng số cách tô bảng 1\times n bởi q màu, hai cách tô là như nhau nếu nó ở dạng như hình dưới đây.

(Trong hình trên các c_i là các màu.)

Gọi X là tập các bộ (c_1,c_2,\cdots,c_n) với c_i là một trong q màu đã cho với mỗi i. Ký hiệu S_n là nhóm các hoán vị trên \{1,2,\cdots,n\}, G là nhóm con cyclic sinh bởi hoán vị f của S_n, ở đây f(i)=n+1-i\forall i. Ta cho G tác động trên X theo luật f(c_1,c_2,\cdots,c_n)=(c_n,c_{n-1},\cdots,c_1). Như trên đã phân tích, ta chỉ cần đếm số N các quỹ đạo của các phần tử của x theo tác động này là xong. Theo bổ đề Burnside, ta chỉ cần tính F(id)F(f). Dễ thấy F(id)=|X|=q^n theo quy tắc nhân. Để tính F(f), ta chú ý rằng (c_1,c_2,\cdots,c_n)\in X không thay đổi khi tác động f nếu và chỉ nếu c_1=c_n,c_2=c_{n-1},\cdots, vậy cùng theo quy tắc nhân ta có F(f)=q^{[\dfrac{n+1}{2}]}. Như thế đáp số của bài toán là \dfrac{1}{2}(q^n+q^{[\dfrac{n+1}{2}]}).

Bài 2. Cho nq là các số nguyên dương. Chứng minh rằng có

\dfrac{1}{4}(q^{n^2}+2q^{[\dfrac{n^2+3}{4}]}+q^{[\dfrac{n^2+1}{2}]}) cách tô màu bảng vuông n\times n bởi q màu.

Lời giải sơ lược. Lời giải y hệt như trường hợp trên. Ta đánh số các ô của bảng theo kiểu xoáy ốc, chia hai trường hợp n chẵn, lẻ cho dễ đánh số. Tập X bây giờ là tập tất cả các bộ (c_1,c_2,\cdots,c_{n^2}), nhóm G bây giờ là nhóm con cyclic cấp 4 sinh bởi phép quay +90^0 của S_{n^2}.

Chú ý.  Khi n=3,q=n ta có bài số 5 trong VMO 2010.



Bài toán số 6 trong IMO 2009


Bài toán này chắc những ai quan tâm đến IMO đều biết là nó rất khó. Đây là vài cái link hay mà tôi tìm được, những ai muốn đọc có thể tham khảo.

link 1

link 2

link 3

link 4

link 5

Đây là bản pdf mà tôi đã gom lại.

Một số sách nên đọc đối với học sinh các lớp chuyên Toán


Các bạn học sinh chuyên Toán thân mến, giờ sách nhiều quá rồi đúng không? 😛  Chúng mình lại không có thời gian đọc hết chúng! 😀 Trong bài này mình sẽ giới thiệu vài cuốn sách nên đọc theo ý kiến của mình, thuộc các phân môn Hình học, Đại số, Lý thuyết số, và Tổ hợp. Các bạn học sinh và các thầy cô giáo có thể trao đổi thoải mái trong topic này, có thể bình luận về danh sách tôi đưa ra, hay có thể tự mình đưa ra danh sách mới,…Trong danh sách dưới đây tôi sẽ đưa ra đa số sách bằng tiếng Anh, vì lâu quá tôi không biết sách tiếng Việt mấy năm vừa qua viết những gì và sách tiếng Anh có thể tìm trên mạng được. Các bạn bây giờ đọc sách tiếng Anh chắc cũng không vấn đề gì rồi. 😀 Gìơ là danh sách

Tổ hợp

[1] Principles and Techniques in Combinatorics, by Chen Chuan-Chong and Koh Khee-Meng

[2] A Path to Combinatorics for Undergraduates: Counting Strategies,  by Titu Andreescu and Zuming Feng

[3] 102 Combinatorics Problems, by Titu Andreescu and Zuming Feng

Lý thuyết số

[4] Elementary Number Theory, by David M. Burton

[5] 104 Number Theory Problems: From the Training of the USA IMO Team, by Titu Andreescu, Dorin Andrica, and Zuming Feng

[6] Number Theory: Structures, Examples, and Problems, by Titu Andreescu and Dorin Andrica

Hình học

[7] Toán nâng cao Hình học 10,  Nguyễn Minh Hà, NXB GD

[8] Các bài toán Hình học phẳng, V.V. Prasolov

Đại số

[9] Phương trình hàm, Nguyễn Văn Mậu, NXB GD

[10] Bài toán hàm số qua các kỳ thi Olympic, Nguyễn Trọng Tuấn, NXB GD

[11] Các bài giảng về phương trình hàm, bất đẳng thức,… của Pierre Bronsztein và các đồng nghiệp

[12] Đa thức và ứng dụng, Nguyễn Văn Mậu, NXB GD

IMO 2009


Danh sách các bạn thuộc đội tuyển năm nay

1.Hà Khương Duy, lớp 12A1 Toán,Khối THPT chuyên ĐHKHTN-ĐHQG Hà Nội.

2.Nguyễn Xuân Cương, lớp 12 Toán 1,THPT chuyên Nguyễn Trãi,Hải Dương.

3.Nguyễn Hoàng Hải, lớp 12A1 ,THPT chuyên Vĩnh Phúc,Vĩnh Phúc.

4.Phạm Đức Hùng, lớp 11 Toán,THPT NK Trần Phú,Hải Phòng.

5.Phạm Hy Hiếu, lớp 11 Toán,PT NK ĐHKHTN-ĐHQG TP Hồ Chí Minh.

6.Tạ Đức Thành, lớp 11 Toán,THPT CHV,Phú Thọ

Các bài toán của ngày thứ  nhất:

Bài 1. Cho n là một số nguyên dương và a_1,\cdots, a_kk>1 số nguyên đôi một khác nhau trong \{1,2,\cdots, n\} sao cho n|a_i(a_{i+1}-1) với i=1,2,\cdots, k-1. Chứng minh rằng n không chia hết a_k(a_1-1).

Bài 2. Cho ABC là một tam giác có tâm đường tròn ngoại tiếp O.  Các điểm P,Q nằm trên các cạnh CA, AB tương ứng. Gọi K,L,M lần lượt là trung điểm của các đoạn thẳng BP,CQ,PQ. Chứng minh rằng nếu PQ là tiếp tuyến của đường tròn (KLM) thì OP=OQ.

Bài 3.  Gỉa sử (s_i) là dãy tăng ngặt các số nguyên dương sao cho các dãy con (s_{s_i})(s_{s_i+1}) là các cấp số cộng. Chứng minh rằng dãy số đã cho cũng là một cấp số cộng.

Đề ngày 2 sẽ có trong comment dưới đây.

Tập hợp và tập hợp con


Trong bài này chúng ta sẽ quan tâm đến các tập hợp nhưng không quan tâm đến tính chất của các phần tử của nó.

Bài 1. Chứng minh rằng số tập con của tập có n phần tử bằng 2^n.

Lời giải. Dùng phương pháp quy nạp theo n hoặc chú ý là mỗi tập con sẽ ứng với một xâu nhị phân có độ dài n.
Bài 2. Cho 1978 tập hợp A_{1},\cdots,A_{1978} thoả mãn các tính chất sau
a)|A_i\cap A_j|=1\forall i<j;
b)|A_i|=40\forall i.
Chứng minh rằng |\cap A_i|=1.
Lời giải. Gỉa sử ngược lại, khi đó giao của các tập hợp phải bằng rỗng. Gỉa sử m là số nguyên dương lớn nhất sao cho trong các tập đó ta tìm được m tập có giao khác rỗng. Không giảm tổng quát gọi các tập đó là A_1,A_2,\cdots,A_m\{x\}=\cap_{i=1}^mA_i, cố định A_1, trong 1977 tập còn lại vì mỗi tập giao với A_1 tại đúng một phần tử và chúng đôi một giao nhau đúng một phần tử, suy ra x thuộc ít nhất [1977/40]+1=50 tập trong 1977 tập này, suy ra m\geq 51. Vì x không thuộc A_{m+1} nên x sẽ không thuộc m tập A_i\cap A_{m+1}, đương nhiên m tập này đôi một rời nhau và là các tập con của A_{m+1}, suy ra m\leq 40, vô lý! Bài toán được giải hoàn toàn.
Bài 3. Tìm số các bộ ba có thứ tự các tập (A,B,C) sao cho A\cup B\cup C=\{1,2,\cdots,2003\}A\cap B\cap C=\emptyset.
Lời giải. Mỗi bộ ba như vậy ứng với một xâu (a_1,a_2,\cdots,a_{2003})\in \{1,2,3,4,5,6\}^{2003}, vì mỗi phần tử i chỉ có thể thuộc A,B,C,A\cap B,B\cap CC\cap A. Đáp số 6^{2003}.
Bài 4. Có bao nhiêu cặp có thứ tự tập hợp con không giao nhau của tập hợp gồm n phần tử?
Lời giải. Kí hiệu một cặp nào đó như đầu bài là (A_1,A_2). Nếu |A_1|=k thì chúng ta sẽ có C_n^k cách chọn A_1, sau khi chọn A_1 rồi thì số cách chọn A_2 bằng số cách chọn một tập con của tập S-A_1, tập này có n-k phần tử (S là tập có n phần tử trong đầu bài), hay số cách chọn A_2 bằng 2^{n-k}. Vậy đáp số của bài toán là \sum_{k=0}^n C_n^k2^{n-k}=(2+1)^n=3^n.
Cách tiếp cận khác: Mỗi cặp như vậy sẽ ứng với một xâu (a_1,a_2,\cdots,a_n)\in\{0,1,2\}^n vì mỗi phần tử của S có thể thuộc A_1, hoặc A_2, hoặc không thuộc cả hai tập đó.

Bài 5. Tập Xn phần tử. Đối với cặp có thứ tự tập con (A_1,A_2) của X, ta tính số phần tử của A_1\cap A_2. Chứng minh rằng tổng các số nhận được bằng n4^{n-1}.
Lời giải. Gỉa sử (A_1,A_2) là một cặp tập con của X, |A_1\cap A_2|=kH=A_1\cap A_2. Ta thấy có C_n^k cách chọn H, sau khi đã chọn H rồi thì số cách chọn (A_1,A_2) bằng số cách chọn cặp (B_1,B_2) các tập con rời nhau của tập X-H, vì tập này có n-k phần tử nên số các cặp (B_1,B_2) bằng 3^{n-k}. Vậy đáp số của bài toán là \sum_{k=0}^nkC_n^k3^{n-k}=n4^{n-1}.
Cách tiếp cận khác: Có 4^n cặp tập (A_1,A_2), chia các cặp này thành các bộ bốn \{(A_1,A_2),(\overline{A}_1,A_2),(A_1,\overline{A}_2),(\overline{A}_1,\overline{A}_2)\}, mỗi phần tử của X sẽ thuộc đúng một trong bốn giao hình thành từ bộ này, do đó tổng đối với bộ này bằng n, mà có đúng 4^{n-1} bộ nên ta có điều phải chứng minh.

Bài 6. Đối với mỗi số nguyên dương n, tìm số nguyên dương k lớn nhất sao cho trong một tập hợp có n phần tử có thể chọn ra k tập con của nó đôi một giao nhau.
Lời giải. Gọi X là một tập có n phần tử và a là một phần tử của nó. Xét 2^{n-1} tập con của X có dạng \{a\}\cup A với A là một tập con của tập X-\{a\}, rõ ràng các tập con này là đôi một giao nhau (cách chọn như vậy là dễ nhất và đây cũng là chìa khoá cho lời giải). Mặt khác với mỗi cách chọn lớn hơn 2^{n-1} tập con của X, bao giờ cũng tồn tại hai tập trong cùng một bộ \{A,\overline{A}\} và hai tập này giao nhau bằng rỗng. Vậy đáp số của bài toán là 2^{n-1}.

Bài 7. Gỉa sử trong tập hữu hạn X chọn ra 50 tập hợp con A_1,A_2,\cdots,A_{50} sao cho mỗi tập này chứa hơn một nửa phần tử của X. Chứng minh rằng tồn tại tập con A của X thoả mãn các điều kiện sau
a)|A|<6, và
b)A\cap A_i\not =\emptyset.

Bài 8(APMO 1998). Cho F_n là tập tất cả các n-bộ (A_1,A_2,\cdots,A_n) sao cho mỗi A_i là một tập con của tập \{1,2,\cdots,2009\}. Tính \sum_{(A_1,A_2,\cdots,A_n)\in F_n}|A_1\cup A_2\cup\cdots\cup A_n|.

Bài 9(RMC 2006). Một tập M gồm 4 số nguyên dương được gọi là liên thông nếu với mỗi x trong M ít nhất một trong các số x-1,x+1 thuộc M. Cho U_n là số các tập con liên thông của tập \{1,2,\cdots,n\}.
a)Tính U_7;
b)Tìm n nhỏ nhất để U_n\geq 2006.

Bài 10(RMC 2006). Tìm số lớn nhất các tập con của tập \{1,2,\cdots,2006\} sao cho mỗi hai tập con khác nhau trong chúng có giao là một tập có 2004 phần tử.

Các tập hợp số


Bài 1(APMO 2004). Tìm tất cả các tập hữu hạn khác rỗng S các số nguyên dương sao cho \dfrac{i+j}{\gcd (i,j)}\in S\forall i,j\in S.
Lời giải. S=\{2\}.
Bài 2(Rumani TST 2008). Cho n>1 là một số nguyên dương. Tìm tất cả các tập A gồm n số nguyên sao cho tổng của tất cả các phần tử của mỗi tập con khác rỗng của A không chia hết cho n+1.
Lời giải. Các phần tử của A bằng nhau theo modulo n+1, chúng đồng dư với p, ở đây \gcd (p,n+1)=1.
Bài 3(Rumani TST 2007). Tìm tất cả các tập con A của tập các số nguyên dương sao cho A có ít nhất 2 phần tử và với mỗi x,y\in A (x\not =y) chúng ta có \dfrac{x+y}{\gcd (x,y)}\in A.
Lời giải. Xét hai trường hợp các phần từ đôi một không nguyên tố và có hai phần tử nguyên tố. Đáp số \mathbb{N}^*,\mathbb{N}^*-\{1\},\mathbb{N}^*-\{2\},\mathbb{N}^*-\{1,2\}\{n,n(n-1)\}(n>2).
Bài 4. (Rumani TST 2002) Tìm tất cả các tập AB sao cho
a)A\cup B=\mathbb{Z};
b)Nếu x\in A thì x-1\in B;
c)Nếu x,y\in B thì x+y\in A.
Lời giải. A=\mathbb{Z},B=\mathbb{Z}A=\{2k|k\in\mathbb{Z}\} , B=\{2k+1|k\in\mathbb{Z}\}.

Bài 5. Cho tập hợp khác rỗng M\subset\mathbb{Q} thoả mãn hai điều kiện
a)Nếu a\in Mb\in M thì a+b\in Mab\in M;
b)Nếu r\in\mathbb{Q} thì xảy ra đúng một trong ba khả năng sau r\in M,-r\in M,r=0.
Chứng minh rằng M là tập các số hữu tỷ dương.

Bài 6(RMC 2004). Kí hiệu \mathbb{P} là tập tất cả các số nguyên tố. Gỉa sử rằng M là một tập con của \mathbb{P} thoả mãn các điều kiện sau
a)|M|>2;
b)Với mỗi tập con thực sự, khác rỗng và hữu hạn A của M , các ước nguyên tố của số \prod_{p\in A}p-1 cũng thuộc M.
Chứng minh rằng M=\mathbb{P}.

Bài 7(Romania TST 2004). Cho A là một tập con của \mathbb{Z}^+ có các tính chất
a)Nếu a\in A thì tất cả các ước dương của a cũng thuộc A;
b)Nếu a,b\in A1<a<b thì 1+ab\in A;
c)|A|>2.
Chứng minh rằng A=\mathbb{Z}^+.

Bài 8(RMC 2006). Cho A là tập các số nguyên không âm có ít nhất hai phần tử sao cho nếu a,b\in A, a>b thì số \dfrac{\text{lcm}\, (a,b)}{a-b}\in A. Chứng minh rằng A có đúng hai phần tử.

Bài 9(RMC 2006). Xét các tập A=\{\sqrt{\dfrac{1}{a}+\dfrac{1}{b}}|a,b\in\mathbb{Z}^+,a\not =b\}  và B=\{\sqrt{\dfrac{1}{x}+\dfrac{1}{y}+\dfrac{1}{z}}|x,y,z\in\mathbb{Z}^+,x>y>z\}.
Chứng minh rằng A\cap B chứa vô hạn các số hữu tỷ và vô hạn các số vô tỷ.
Lời giải. Quan tâm đến phương trình \dfrac{1}{n}=\dfrac{1}{x}+\dfrac{1}{y}.
Bài 10(RMC 2007). Tìm tất cả các tập con khác rỗng A của tập \{2,3,\cdots\} sao cho với mỗi n\in A, cả hai số n^2+4[\sqrt{n}]+1 cũng thuộc A.
Bài 11(France 2002). Xét 2002 số hữu tỉ x_1,x_2,\cdots,x_{2002}. Biết rằng với mỗi tập con I gồm 7 phần tử của tập \{1,2,\cdots,2002\} tồn tại tập con J gồm 11 phần tử của tập \{1,2,\cdots,2002\} sao cho \dfrac{1}{7}\sum_{i\in I}x_i=\dfrac{1}{11}\sum_{j\in J}x_j. Chứng minh rằng x_1=x_2=\cdots=x_{2002}.

Một đồng dư modulo nguyên tố


Người dịch: Nguyễn Trung Tuân
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=kl. 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

\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}).

k\leq p\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.

Nguyên lý bù-trừ


Mở đầu

Bài viết xem như sự mở đầu của phương pháp SÀNG trong các bài toán đếm. Ở phương pháp này, khi muốn đếm số phần tử của một tập A, ta bắt đầu với một tập B chứa A, sau đó tìm cách loại đi các phần tử không nằm trong A.

Chúng ta biết rằng nếu AB là các tập hữu hạn rời nhau thì |A\cup B|=|A|+|B|, tổng quát hơn ta có: Nếu AB là các tập hữu hạn bất kỳ(không nhất thiết rời nhau) thì  |A\cup B|=|A|+|B|-|A\cap B|, đây chính là nguyên lý bù-trừ cho hai tập hợp, dễ hiểu tại sao người ta lại gọi đây là nguyên lý bù trừ. Với n>1 tập hợp ta có định lý sau

Định lý. Nếu A_1,A_2,\cdots,A_n là các tập hữu hạn thì |\cup_{i=1}^nA_i|=\sum_{1\leq i\leq n}|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|+...+(-1)^{n+1}|\cap_{1\leq i\leq n}A_i|.

Ta sẽ chứng minh rằng rằng mỗi phần tử trong \cup_{i=1}^nA_i được đếm đúng một lần trong vế phải. Gọi x là một phần tử trong hợp đó và nó nằm trong dúng m tập A_i, khi đó trong vế phải nó sẽ được đếm đúng C_m^1-C_m^2+\cdots+(-1)^{m+1}C_m^m=1 lần (lưu ý (1-1)^m=0). Định lý được chứng minh.

Ngoài cách chứng minh trên các bạn có thể chứng minh Định lý bằng phương pháp quy nạp toán học, tôi chọn giới thiệu cách chứng minh đó vì phong cách Tổ hợp của nó.

Một áp dụng đẹp của nguyên lý bù-trừ là bài toán Bernoulli-Euler về các bức thư sai địa chỉ: Có n>1 bức thư khác nhau phải gửi đến n địa chỉ khác nhau. Có bao nhiêu cách gửi mà các bức thư đều đến không đúng địa chỉ của mình? Theo ngôn ngữ ánh xạ, bài toán được phát biểu như sau: Có bao nhiêu song ánh từ S={1,2,…,n} đến chính S sao cho nó không có điểm cố định? Ta đếm số các song ánh có điểm cố định, số này bằng C_n=|\cup_{1\leq i\leq n}A_i|, ở đây A_i là tập các song ánh nhận i làm điểm cố định. Theo nguyên lý bù-trừ dễ có C_n=\sum_{k=1}^nC_n^k(-1)^{k+1}(n-k)! và đáp số của bài toán là D_n=n!-C_n.

Bài tập.

Bài 1. Tìm số các số nguyên dương trong {1,2,…,500} chia hết cho 2 hoặc 3 hoặc 5.

Bài 2. Tính giá trị của phi hàm Euler tại n theo phân tích chính tắc của n.

Bài 3. Chứng minh nguyên lý bù-trừ bằng quy nạp toán học.

Bài 4. Cho X là một tập hữu hạn và A,B,C là các tập con của nó. Chứng minh rằng |\bar{A}\cap B|=|B|-|A\cap B||\bar{A}\cap\bar{B}\cap C|=|C|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.

Bài 5. Tìm số các số nguyên trong tập {1,2,…,1000} không chia hết cho 5, không chia hết cho 7, nhưng chia hết cho 3.

Bài 6. Có bao nhiêu số nguyên dương n sao cho n là ước của ít nhất một trong hai số 10^{40}20^{30}?

Bài 7. Với mỗi số nguyên dương n>1, gọi A_n là số các song ánh từ S đến S sao cho f(k) khác k+1 với mỗi k=1,2,…,n-1.

a)Tính A_n;

b)Chứng minh rằng A_n=D_n+D_{n-1} với mỗi n>1.

Bài 8. Tìm số các số nguyên dương là ước của ít nhất một trong các số 10^{60},20^{50},30^{40}.

Bài 9. Với k=1,2,…,1992 cho A_k là một tập với 44 phần tử. Gỉa sử rằng |A_i\cap A_j|=1 với mỗi i,j khác nhau trong {1,2,…,1992}. Tính |\cup_{i=1}^{1992}A_i|.

Bài 10. Cho A_1,A_2,\cdots,A_n là n tập hữu hạn. Chứng minh rằng |\cup_{i=1}^nA_i|\geq \sum_{i=1}^n|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|. Sử dụng bất đẳng thức này để giải bài toán sau: Một hoán vị của {1,2,…,2n} được gọi là có tính chất P nếu có ít nhất hai số dạng k,n+k đứng cạnh nhau. Chứng minh rằng với mỗi số nguyên dương n, số các hoán vị có tính chất P nhiều hơn số các hoán vị không có tính chất đó.

Bài 11. Cho các số nguyên dương m\leq n và A,B là các tập có n,m phần tử tương ứng. Tìm số các toàn ánh từ A lên B. Từ đó suy ra \sum_{k=0}^n(-1)^kC_n^k(n-k)^n=n!.