Kỳ thi Olympic Toán Sinh viên và Học sinh 2016


Hội Toán học Việt Nam phối hợp với Trường Đại học Quy Nhơn tổ chức kỳ thi Olympic Toán học dành cho Sinh viên và Học sinh Trung học Phổ thông chuyên nhằm góp phần nâng cao chất lượng dạy và học toán, thúc đẩy niềm say mê toán học trong học sinh, phát hiện, bồi dưỡng học sinh giỏi toán. Kỳ thi cũng là một cơ hội giao lưu cho các học sinh giỏi toán với các sinh viên yêu toán và các giảng viên toán tại các trường đại học, cao đẳng và học viện. Continue reading “Kỳ thi Olympic Toán Sinh viên và Học sinh 2016”

Principles and Techniques in Combinatorics


By (author): Chen Chuan-Chong (NUS, Singapore), Koh Khee-Meng (NUS, Singapore)

A textbook suitable for undergraduate courses. The materials are presented very explicitly so that students will find it very easy to read. A wide range of examples, about 500 combinatorial problems taken from various mathematical competitions and exercises are also included.

Contents:

  • Permutations and Combinations
  • Binomial Coefficients and Multinomial Coefficients
  • The Pigeonhole Principle and Ramsey Numbers
  • The Principle of Inclusion and Exclusion
  • Generating Functions
  • Recurrence Relations

Readership: Undergraduates, graduates and mathematicians.

Download

Các tính chất đại số của hệ số nhị thức


Bài 5.1. Cho n là một số nguyên dương. Tìm số hạng lớn nhất của dãy \{C_n^k\}_{k=0}^n.

Bài 5.2. Chứng minh rằng nếu n,k là các số nguyên dương sao cho n>1 thì

a)kC_n^k=nC_{n-1}^{k-1};

b)kC_n^k=(n-k+1)C_n^{k-1}.

Bài 5.3. Chứng minh rằng nếu n,k là các số nguyên dương thì

a)C_n^0+C_{n+1}^1+C_{n+2}^2+\cdots+C_{n+k}^k=C_{n+k+1}^k;

b)C_n^n+C_{n+1}^n+C_{n+2}^n+\cdots+C_{n+k}^n=C_{n+k+1}^{n+1}.

Bài 5.4. Chứng minh rằng nếu n là một số nguyên dương thì

a)C_n^0+C_n^1+\cdots + C_n^n=2^n;

b)C_n^0-C_n^1+\cdots+(-1)^nC_n^n=0;

Continue reading “Các tính chất đại số của hệ số nhị thức”

Tổ hợp


Định nghĩa. Cho một tập An phần tử(n\in\mathbb{N}) và 0\leq k\leq n là một số nguyên. Một k-tổ hợp(một tổ hợp chập k) của A là một tập con k phần tử của A.

Ví dụ 4.1. Các 3-tổ hợp của A=\{a,b,c,d\}\{a,b,c\},\{b,c,d\},\{c,d,a\},\{d,a,b\}\Box.

Số tổ hợp. Cho một tập An phần tử(n\in\mathbb{N}) và 0\leq k\leq n là một số nguyên. Khi đó số k-tổ hợp của A bằng C_n^k=\dfrac{A_n^k}{k!}=\dfrac{n!}{k!(n-k)!}.

Chứng minh. Sự khác nhau giữa một k-tổ hợp và một k-hoán vị chính là một đằng không quan tâm đến thứ tự, trong khi đằng kia có quan tâm đến thứ tự. Tận dụng điều này ta có chứng minh như sau.

Continue reading “Tổ hợp”

Bài tập về Hệ số nhị thức


Download

Lớp trưởng lấy về và chụp cho các bạn mỗi người một bản. Hưng không phải đi chụp nữa, việc này để Tuấn làm, em chỉ cần cho bạn Tuấn mượn bản in là đủ. Tuấn nên lập một quỹ dành cho việc chụp tài liệu, có nhiều môn cần phải chụp tài liệu chứ không riêng môn Toán. Lần sau những việc như thế này lớp trưởng phải chủ động nghĩ và làm, thầy không nói nhiều nữa.

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.