IMC training 2016 (2)


Methods of Counting

Problem 1. How many subsets are there in a set of size 10?

Problem 2. Find the number of squares contained in an 10\times 10 squares array.

Problem 3. A team is to be chosen from 4 girls and 6 boys. The only requirement is that it must contain at least 2 girls. Find the number of different teams that may be chosen.

Problem 4. You wish to give your Aunt Mollie a basket of fruit. In your refrigerator you have six oranges and nine apples. The only requirement is that there must be at least one piece of fruit in the basket (that is, an empty basket of fruit is not allowed). How many different baskets of fruit are possible?

Problem 5. Find the number of ways 30 identical pencils can be distributed among three girls so that each gets at least 1 pencil.

Problem 6. There 7 boys and 3 girls in a gathering. In how many ways can they be arranged in a row so that

1) the 3 girls form a single block?

2) the two end-possitions are occupied by boys and no girls are adjacent?

Problem 7. Between 20000 and 70000, find the number of even integers in which no digit is repeated. Continue reading “IMC training 2016 (2)”

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”

Bài tập về đếm


Bài 1. Cho số nguyên dương n
a) Có bao nhiêu xâu nhị phân độ dài n?
b) Chứng minh rằng số tập con của một tập có n phần tử là 2^n.
c) Có bao nhiêu tập con có số phần tử lẻ của \{1,2,\cdots,n\}?
Bài 2.
a) Có bao nhiêu xâu nhị phân độ dài 12 có đúng 6 chữ số 0?
b) Có bao nhiêu xâu nhị phân độ dài 12 mà số số 0 nhiều hơn số số 1? Continue reading “Bài tập về đếm”

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

Hoán vị tròn


Định nghĩa. Cho A là một tập có n phần tử(n\in\mathbb{N}) và 1\leq r\leq n là một số nguyên. Một r-hoán vị tròn của A là một cách xếp r phần tử nào đó của A lên một đường tròn, hai cách xếp được coi là như nhau nếu chúng sai khác nhau một phép quay. Một n-hoán vị tròn của A sẽ gọi đơn giản là một hoán vị tròn của A.

Số hoán vị tròn. Cho A là một tập có n phần tử(n\in\mathbb{N}) và 1\leq r\leq n là một số nguyên. Khi đó số các r-hoán vị tròn của A bằng Q_n^r=\dfrac{A_n^r}{r}. Nói riêng, số các hoán vị tròn của A bằng Q_n^n=(n-1)!.

Chứng minh. Ta sẽ dùng nguyên lý chia để chứng minh công thức này.

Nguyên lý chia. Nếu tập An phần tử được phân hoạch thành các tập hợp có k phần tử thì số khối của phân hoạch bằng \dfrac{n}{k}.

Tập các r-hoán vị tuyến tính có thể phân hoạch thành các phần nhỏ sao cho hai hoán vị tuyến tính thuộc cùng một phần nếu chúng xác định cùng một hoán vị tròn. Vì số các hoán vị tuyến tính trong mỗi phần bằng r nên số các hoán vị tròn bằng Q_n^r=\dfrac{A_n^r}{r}\Box.

Ví dụ 3.1. Có bao nhiêu cách để 5 bé trai và 3 bé gái ngồi quanh một bàn tròn nếu

a)Không có thêm điều kiện gì?

b)Bé trai T_1 và bé gái G_1 không ngồi cạnh nhau?

c)Không có bé gái nào ngồi cạnh nhau?

Đáp số. a)Q_8^8.

b)6!\times 5.

c)4!\times 5\times 4\times 3\Box.

Ví dụ 3.2. Tìm số cách xếp n cặp vợ chồng ngồi quanh một bàn tròn sao cho

a)Đàn ông và đàn bà ngồi xen kẽ nhau;

b)Mỗi người đàn bà ngồi cạnh chồng của cô ấy.

Hướng dẫn. a)Chọn chỗ cho đàn ông trước sau đó đến đàn bà, đáp số (n-1)!\times n!.

b)Coi một cặp là một người, xếp n người này, và sau đó xếp vị trí vợ-chồng, đáp số (n-1)!\times 2^n\Box.

Ví dụ 3.3. Người ta định xếp 6 cậu bé và 5 cô bé ngồi xung quanh một cái bàn. Tìm số cách xếp nếu

a)Không có thêm điều kiện gì;

b)Không có hai cô bé nào ngồi cạnh nhau;

c)Tất cả các cô bé ngồi liền nhau;

d)Cô bé G ngồi cạnh hai cậu bé T_1,T_2.

Đáp số. a)10!.

b)5!\times A_6^5.

c)6!\times 5!.

d)2\times 8!\Box.

Ví dụ 3.4. Cho n,k là các số nguyên dương. Chứng minh rằng có \dfrac{(kn)!}{n^k} cách xếp kn người ngồi xung quanh k cái bàn khác nhau sau cho mỗi bàn có n người.

Hướng dẫn. Chọn một n-hoán vị tròn xếp vào bàn 1, sau đó bàn 2,…\Box.

Đếm bằng truy hồi (2)


C11. Cho số nguyên dương n. Từ tập các hoán vị f của [n] thỏa mãn f(i)\geq i-1\,\,\forall i=2,3,\ldots,n ta chọn ngẫu nhiên một hoán vị, kí hiệu g. Gọi p_n là xác suất để hoán vị đó thỏa mãn g(i)\leq i+1\,\,\forall i=1,2,\ldots,n. Tìm tất cả các số nguyên dương n để p_n>\frac{1}{3}.

C12.  Cho số nguyên dương n. Gọi a_n là số các xâu nhị phân độ dài n không chứa khối 010, b_n là số các xâu nhị phân độ dài n không chứa các khối dạng 00111100. Chứng minh rằng với mỗi số nguyên dương n, ta có b_{n+1}=2a_n.

C13. Có bao nhiêu số tự nhiên n1000 chữ số thỏa mãn đồng thời hai điều kiện

1/. Tất cả các chữ số của n là lẻ;

2/. Giá trị tuyệt đối của hiệu hai chữ số liên tiếp bất kì của n bằng 2.

C14. Cho số nguyên dương n. Gọi O_n là số các xâu nhị phân (x_1,x_2,\ldots,x_n,y_1,y_2,\ldots,y_n) thỏa mãn \sum x_iy_i là số lẻ, và E_n là số các xâu nhị phân (x_1,x_2,\ldots,x_n,y_1,y_2,\ldots,y_n) thỏa mãn \sum x_iy_i là số chẵn. Chứng minh rằng \frac{O_n}{E_n}=\frac{2^n-1}{2^n+1}.

C15. Tìm số các số nguyên dương n thỏa mãn 4\leq n\leq 1023 và trong biểu diễn nhị phân của nó không có ba chữ số liên tiếp bằng nhau.

C16. Bảng chữ cái của một loại ngôn ngữ nào đó chỉ có hai chữ cái AB. Các từ trong ngôn ngữ này phải thỏa mãn đồng thời các điều kiện sau

1/. Không có từ với độ dài bằng 1;

2/. Chỉ có hai từ với độ dài bằng 2ABBB;

3/. Một dãy các chữ cái có độ dài n>2 là một từ khi và chỉ khi nó được tạo từ một từ khác có độ dài nhỏ hơn n theo cách sau: Các chữ A trong từ đó được giữ nguyên, mỗi chữ B của nó sẽ được thay bởi một từ khác (hai chữ B khác vị trí có thể được thay bởi hai từ khác nhau hoặc không).

Chứng minh rằng với mỗi số nguyên dương n, số các từ có độ dài bằng n trong ngôn ngữ đó là \frac{2^n+2\cdot (-1)^n}{3}.

Continue reading “Đếm bằng truy hồi (2)”

Đếm bằng truy hồi (1)


C1. Cho số nguyên n>1. Hãy tìm số các hoán vị (a_1,a_2,\cdots,a_n) của \{1,2,\cdots,n\} sao cho tồn tại duy nhất i để a_i>a_{i+1}.

C2. Cho n>1 là một số nguyên dương. Tìm số các tập con của \{1,2,\cdots,n\} sao cho trong mỗi tập con có ít nhất hai phần tử là hai số nguyên liên tiếp.

C3. Cho n>1 thí sinh ngồi quanh một bàn tròn. Hỏi có bao nhiêu cách phát đề sao cho hai thí sinh ngồi cạnh nhau luôn có đề khác nhau, biết rằng trong ngân hàng đề có đúng m>1 đề và mỗi đề có nhiều bản.

C4. Cho một mặt cầu. Một đường tròn lớn của mặt cầu là đường tròn nằm trong một mặt phẳng đi qua tâm của cầu và nằm trên mặt cầu. 5 đường tròn lớn khác nhau chia mặt cầu thành n phần. Tìm giá trị lớn nhất và bé nhất của n.

C5. Một tập hữu hạn các số nguyên dương được gọi là tốt nếu mỗi phần tử của nó ít nhất bằng số phần tử của nó. (Tập rỗng cũng được xem là tốt) Gọi a_n là số tập con tốt của [n] mà không chứa hai số liên tiếp, và b_n là số các tập con của [n] mà hai phần tử bất kì khác nhau ít nhất 3. Chứng minh rằng a_n=b_n với mỗi n\geq 0.

C6. Sử dụng các chữ số 0,1,2,3,4 ta có thể lập bao nhiêu dãy 10 chữ số sao cho hay chữ số cạnh nhau vênh nhau 1?

C7. Gọi A_n là kí hiệu tập các đoạn mã độ dài n hình thành bởi sử dụng các chữ a,b,c sao cho không có các chữ a hay b đứng cạnh nhau. B_n là tập các đoạn mã độ dài n hình thành từ các chữ a,b,c sao cho không có 3 chữ phân biệt đứng cạnh nhau. Chứng minh rằng |B_{n+1}|=3|A_n|\forall n\geq 1.

Continue reading “Đếm bằng truy hồi (1)”

Đếm


Bài 1. Cho n,r là các số nguyên dương thỏa mãn 1\leq r\leq n. Xét tất cả các tập con r phần tử của tập \{1,2,\cdots,n\}, mỗi tập con này có phần tử nhỏ nhất. Chứng minh rằng trung bình cộng của các phần tử nhỏ nhất này bằng \dfrac{n+1}{r+1}.

Bài 2. Cho tập S=\{1,2,\cdots,2002\}. Gọi T là tập gồm tất cả các tập con khác rỗng của tập S. Với mỗi X\in T, kí hiệu m(X) là trung bình cộng của các số thuộc X. Tính trung bình cộng của các m(X) với X chạy khắp T.

Bài 3. Tìm kết quả học tập ở một lớp học người ta thấy: Hơn \dfrac{2}{3} số học sinh đạt điểm giỏi ở môn Toán cũng đạt điểm giỏi môn Lý, hơn \dfrac{2}{3} số học sinh đạt điểm giỏi ở môn Lý cũng đạt điểm giỏi môn Văn, hơn \dfrac{2}{3} số học sinh đạt điểm giỏi ở môn Văn cũng đạt điểm giỏi môn Sử, và hơn \dfrac{2}{3} số học sinh đạt điểm giỏi ở môn Sử cũng đạt điểm giỏi môn Toán. Chứng minh rằng trong lớp có ít nhất một học sinh giỏi cả 4 môn trên.

Bài 4. Một đơn vị kiểm lâm muốn lập lịch đi tuần tra rừng cho cả năm 2006 với các yêu cầu sau

1/. Số ngày đi tuần tra nhiều hơn một nửa số ngày trong năm

2/. Không có hai ngày đi tuần tra nào cách nhau đúng một tuần

Chứng minh rằng có thể lập được lịch đi tuần. Hỏi có thể lập được bao nhiêu lịch đi tuần như vậy? (Năm 2006365 ngày)

Bài 5. Có bao nhiêu số tự nhiên chia hết cho 9 mà mỗi số gồm nhiều nhất 2008 chữ số và trong đó có ít nhất hai chữ số 9?

Bài 6. Có bao nhiêu bộ bốn các số nguyên dương lẻ (x_1,x_2,x_3,x_4) thỏa mãn x_1+x_2+x_3+x_4=98.

Bài 7. Cho tập Sn>1 phần tử. Có bao nhiêu cách chọn hai tập con (không kể thứ tự) không cần khác nhau của S sao cho hợp của hai tập này bằng S?

Bài 8. Cho số nguyên dương n>1 và một hình vuông cỡ (n-1)\times (n-1). Chia hình vuông này thành (n-1)^2 ô vuông đơn vị theo cách thông thường. Mỗi một trong n^2 đỉnh của các ô vuông này được tô bởi một trong hai màu xanh, đỏ sao cho mỗi ô vuông đơn vị có đúng hai đỉnh xanh, hai đỉnh đỏ. Có bao nhiêu cách tô màu như vậy?

Bài 9. 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}.

Bài 10. Cho số nguyên dương n>3. Hỏi một n-giác lồi có tất cả bao nhiêu đường chéo?

Bài 11. Cho số nguyên dương n>4 và một n-giác lồi P. Biết không có 3 đường chéo nào của P đồng quy. Hỏi khi ta kẻ tất cả các đường chéo thì có bao nhiêu giao điểm của các đường chéo này? (Ta chỉ tính các giao điểm nằm bên trong đường chéo)

Continue reading “Đếm”

Nguyên lý bù-trừ 2


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|+\cdots+(-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,\cdots,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.

Continue reading “Nguyên lý bù-trừ 2”

Dùng ánh xạ trong các bài toán Tổ hợp


Để đếm số phần tử của một tập hữu hạn A, ta tìm một tập hữu hạn B có cùng số phần tử như A nhưng dễ đếm hơn.

Nguyên lý ánh xạ. Cho AB là các tập hữu hạn khác rỗng và f:A\to B là một ánh xạ. Khi đó

a)Nếu f là đơn ánh thì |A|\leq |B|;

b)Nếu f là toàn ánh thì |A|\geq |B|;

c)Nếu f là song ánh thì |A|=|B|.

Continue reading “Dùng ánh xạ trong các bài toán Tổ hợp”