Chương 1 Một số kỹ năng giải bài toán đếm Bài toán đếm là một nội dung cơ bản không chỉ dành cho các bài toán thi đại học mà còn rất cần thiết khi giải các bài toán tổ hợp khó trong các kỳ thi học sinh giỏi. Một đặc điểm rất đặc thù của nội dung này là khi giải toán, học sinh thường nhận được các đáp số khác nhau vì những sai sót mà bản thân không nhận ra. Chính vì vậy xây dựng các kỹ năng giải là thực sự cần thiết và nội dung của phần này là trình bày các kỹ năng này.1 Sử dụng các khái niệm cơ bản 1.1 Quy tắc cộng, quy tắc nhân Quy tắc cộng. Nội dung quy tắc: Nếu có m1 cách chọn đối tượng a1 , m2 cách chọn đối tượng a2 , ., mn cách chọn đối tượng an , trong đó cách chọn đối tượng ai (1 ≤ i ≤ n) không phụ thuộc vào bất kì cách chọn đối tượng aj n P (1 ≤ i ≤ n, i 6= j ) thì sẽ có mk cách chọn đối tượng a1 , hoặc a2 ,.
Quy tắc nhân. Nội dung quy tắc: Cho n đối tượng a1 , a2 ,. Nếu có m1 cách chọn đối tượng a1 và với mỗi cách chọn a1 có m2 cách chọn đối tượng a2 , sau đó với mỗi cách chọn a1 , a2 có m3 cách chọn đối tượng a3 ,. Cuối cùng với mỗi cách chọn a1 , a2 , a3 , ., an−1 có mn cách chọn đối tượng an.
Như vậy sẽ có m1 .mn cách chọn các đối tượng a1 , rồi a2 , rồi a3. Sau đây ta xét một số bài toán minh họa: 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.Với sáu chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số gồm bốn chữ số khác nhau và trong mỗi số nhất thiết phải có chữ số 1. Bài giải Gọi số cần lập là abcd. Xét các trường hợp: Trường hợp 1: a = 1 có 1 cách chọn a, có A35 cách chọn các chữ số b, c, d.
Trường hợp 2: a 6= 1. - Nếu b = 1 thì có 1 cách chọn b và có A24 cách chọn c, d; - Nếu c = 1 thì có 1 cách chọn c và có A24 cách chọn b, d; - Nếu d = 1 thì có 1 cách chọn d và có A24 cách chọn b, c; Vậy theo quy tắc cộng có thể lập được 1. Từ thành phố A đến thành phố B có 3 con đường, từ thành phố A đến thành phố C có 2 con đường, từ thành phố B đến thành phố D có 2 con đường, từ thành phố C đến thành phố D có 4 con đường. Không có con đường nào nối thành phố B với thành phố C.
Hỏi có tất cả bao nhiêu con đường nối từ thành phố A đến thành phố D. Bài giải Trường hợp 1: Đi từ A đến B rồi đến D. Có 3 cách đi từ A đến B và có 2 cách đi từ B đến D. Theo quy tắc nhân thì số cách chọn đường đi từ A đến D qua B là 3.2 = 6; Trường hợp 2: Đi từ A đến C rồi đến D.
Có 2 cách đi từ A đến C và có 4 cách đi từ C đến D. Theo quy tắc nhân thì số cách chọn đường đi từ A đến D qua C là 2. Vì cách chọn đường từ A sang D qua B và cách chọn đường từ A sang D qua C không phụ thuộc lẫn nhau, nên theo quy tắc cộng, ta có số con đường để đi từ A sang D là 6 + 8 = 14 (cách). Từ các chữ số 1, 2, 3, 4, 5, 6, 7, 8, 9 có thể lập được bao nhiêu số gồm 4 chữ số khác nhau? Tìm tổng của tất cả các số này.
Bài giải Gọi số cần lập có dạng abcd. Có 9 cách chọn a; Có 8 cách chọn b (b 6= a); Có 7 cách chọn c (c 6= a, c 6= b); Có 6 cách chọn d (d 6= a, d 6= b, d 6= c). Vậy theo quy tắc nhân thì số các số có thể lập được là 9. Số lớn nhất, số nhỏ nhất trong các số dạng này lần lượt là 9876 và 1234 có tổng bằng 11110, nên đối với số bất kì abcd đều tồn tại số a0 b0 c0 d0 , mà 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com abcd + a0 b0 c0 d0 = 11110 Khi đó, ta có đẳng thức: (a+a0 ).10 Từ đó, ta có các đẳng thức a + a0 = b + b0 = c + c0 = d + d0 = 10 a 6= a0 ⇔ b 6= b0 ⇔ c 6= c0 ⇔ d 6= d0 Bởi vậy, nếu abcd có các chữ số không trùng nhau thì a0 b0 c0 d0 cũng có các 1 chữ số không trùng nhau.6 cặp số abcd, a0 b0 c0 d0 gồm 4 2 chữ số không trùng nhau thuộc tập {1, 2, 3, 4, 5, 6, 7, 8, 9} Vậy tổng tất cả các số dạng trên là : 1.
Một con ngựa trên bàn cờ vua 8x8. Hỏi có bao cách di chuyển con ngựa trên bàn cờ. Bài giải Các ô của bàn cờ có thể đặt theo quy tắc aij (i=1.8) a11 có 2 cách di chuyển. a12 có 3 cách di chuyển.
a13 , a14 , a22 có 4 cách di chuyển. a23 , a24 có 6 cách di chuyển. a33 , a34 , a44 có 8 cách di chuyển. Lấy đối xứng các vị trí trên qua 4 trục đối xứng của bàn cờ, ta có tổng số cách là: n = 4.
Cho bàn cờ vua 8x8. Có bao nhiêu cách chọn ra 1 ô trắng và 1 ô đen? Có bao cách chọn 1 ô trắng, 1 ô đen cùng nằm trên 1 hàng hay 1 cột? Bài giải Trên bàn cờ có 32 ô trắng, 32 ô đen. Có 32 cách chọn ra một ô đen, 32 cách chọn một ô trắng. Vậy số cách chọn n1 =32.
Có 32 cách chọn một ô trắng. Số ô đen cùng hàng, cùng cột với ô trắng đã chọn ra là 8. Vậy số cách chọn n2 =32. 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Bài 6 Có 28 quân domino ở 2 đầu có x,y chấm 0 ≤ x, y ≤ 6.
Có bao nhiêu cách chọn ra 2 quân domino có thể nối với nhau (số chấm ở một đầu của quân này bằng số chấm ở một đầu quân khác). Bài giải Lấy một quân domino bất kỳ nó thuộc một trong 2 loại: Loại 1 (7 quân): (0,0), (1,1),. Loại 2 (21 quân): có số chấm 2 đầu khác nhau. - Nếu quân domino chọn ra là loại 1 (sẽ có 7 cách chon) sẽ được nối với 6 quân khác.
Vậy số cặp nối được trong trường hợp này là: n1 = 7. - Nếu quân domino chọn ra là loại 2 (sẽ có 21 cách chọn), sẽ được nối với 12 quân khác. Vậy số cặp nối đươc trong trường hợp này là n2 = 21. Theo quy tắc cộng thì số cách nối đươc là 252+42=294 (kể cả thứ tự).
Vì thứ tự giữa 2 đầu của quân domini được xác định, và mỗi cặp 2 quân 294 domino nối được đến 2 lần, ta suy ra số cặp nối được là n = = 147.2 Hoán vị Hoán vị không lặp Định nghĩa: Cho một tập hợp gồm n (n ≥ 1) phần tử. Mỗi cách sắp xếp n phần tử này theo một thứ tự nào đó (mỗi phần tử có mặt đúng một lần) được gọi là một hoán vị của n phần tử đã cho. Kí hiệu số hoán vị của n phần tử bằng Pn Ta có công thức Pn = n! Sau đây ta xét một số bài oán minh họa: Bài 7.Với năm chữ số 1, 2, 3, 4, 5 có thể lập được bao nhiêu số gồm năm chữ số khác nhau? Bài giải Mỗi số cần lập là một hoán vị của năm chữ số đã cho. Vậy số các số lập được bằng số hoán vị của năm phần tử bằng P5 = 5! = 120 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Trong một hội nghị có 5 báo cáo viên A, B, C, D, E mỗi người báo cáo một lần? 1. Có bao nhiêu cách xếp thứ tự cho báo cáo viên. Có bao nhiêu cách xếp thứ tự cho báo cáo viên nếu yêu cầu báo cáo viên B báo cáo ngay sau báo cáo viên A? 3. Có bao nhiêu cách xếp thứ tự cho báo cáo viên nếu B không báo cáo trước A? Bài giải 1.
Số cách xếp thứ tự cho báo cáo viên bằng 5! = 120 2. B báo cáo ngay sau A ta thay thế bằng một cặp báo cáo viên X= AB. Khi đó, xem X như là một báo cáo viên. Vậy số cách là n2 = 4! = 24.
Trong mọi cách sắp xếp khả năng A đứng trước B hay đứng sau B là như nhau. 1 Vậy số cách sắp xếp B không báo cáo trước A là. 2 Bài 9 Có bao nhiêu cách xếp 5 người đàn ông, 5 người đàn bà xung quanh một bàn tròn 10 ghế sao cho không có 2 người đàn ông hoặc 2 người đàn bà nào ngồi cạnh nhau. Bài giải Lấy 1 ghế bất kỳ.
Nếu xếp 1 người đàn ông thì ghế tiếp theo là của đàn bà. Số cách xếp 5 đàn ông vào vị trí có sẵn là 5!, số cách xếp 5 đàn bàn vào vị trí là 5!. Số cách xếp theo vị trí này là 5!5!. Nếu xếp 1 người đàn bà thì số cách xếp tương tự bằng 5!5!.
Hoán vị có lặp Định nghĩa: Hoán vị trong đó mỗi phần tử xuất hiện ít nhất một lần được gọi là hoán vị có lặp. Số hoán vị lặp của n phần tử thuộc k loại, mà các phần tử loại i (1 ≤ i ≤ k ) xuất hiện ni lần được kí hiệu là P (n1 , n2 , ., nk ) và được tính bằng công thức n! P (n1 , n2 , .nk ! Sau đây ta xét một số bài toán minh họa: Bài 10. Với các chữ số 1, 2, 3, 4, 5, 6 có thể lập được bao nhiêu số gồm chín chữ số, trong đó mỗi chữ số 1, 2, 3, 4 xuất hiện đúng một lần, chữ số 5 xuất hiện đúng hai lần và chữ số 6 xuất hiện đúng ba lần. 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Bài giải Xét một số tùy ý x = 154626356 và kí hiệu các vị trí của x một cách hình thức, ta có x = a1 a2 a3 a4 a5 a6 a7 a8 a9.
Khi đó, mỗi số x tương ứng với một hoán vị lặp của chín phần tử a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9. Số các hoán vị khác nhau của chín phần tử ai (1 ≤ i ≤ 9) là 9!