Tài liệu MỘT SỐ DẠNG BÀI TOÁN TỔ HỢP

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN VIỆT HÙNG MỘT SỐ DẠNG BÀI TOÁN TỔ HỢP LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội - 2013 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN VIỆT HÙNG MỘT SỐ DẠNG BÀI TOÁN TỔ HỢP Chuyên ngành: Phương pháp toán sơ cấp Mã số: 60 46 40 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. NGUYỄN VŨ LƯƠNG Hà Nội - 2013 Mục lục LỜI MỞ ĐẦU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Các bài toán về tập hợp iii 1 1.1 Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Bài tập đề nghị . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 Các bài toán về phép đếm 12 2.1 Tóm tắt lý thuyết . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Sử dụng phép đếm để chứng minh các đẳng thức về tổ hợp . . . 19 2.4 Bài tập đề nghị . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3 Các bài toán về số tổ hợp, chỉnh hợp và hoán vị 28 3.1 Chứng minh các hệ thức về số tổ hợp, chỉnh hợp và hoán vị . . 28 3.2 Nhị thức Newton và bài toán tổng tổ hợp . . . . . . . . . . . . . 35 3.3 Nhị thức Newton và số phức . . . . . . . . . . . . . . . . . . . . 41 3.4 Sử dụng đạo hàm, tích phân và nhị thức Newton để xây dựng các đẳng thức tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . 44 3.5 Bài tập đề nghị . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4 Một số bài toán tổ hợp nâng cao 56 4.1 Các bài toán sử dụng quan hệ truy hồi . . . . . . . . . . . . . . 56 4.2 Các bài toán sử dụng song ánh . . . . . . . . . . . . . . . . . . 60 4.3 Phương pháp quỹ đạo . . . . . . . . . . . . . . . . . . . . . . . 62 4.4 Một số dạng bài toán khác . . . . . . . . . . . . . . . . . . . . . 67 i 5 Các bài toán sử dụng nguyên lý Dirichlet 77 5.1 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.2 Các ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.3 Bài tập đề nghị . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . . . . . 89 iii Lời mở đầu LỜI MỞ ĐẦU Các bài toán tổ hợp xuất hiện một cách thường xuyên trong các đề thi học sinh giỏi Quốc gia, Quốc tế và chúng luôn được xem là một trong những dạng toán khó nhất đối với phần lớn học sinh. Hẳn là mỗi chúng ta đều đã từng phải rất đau đầu trước một bài toán tổ hợp. Đặc điểm của toán tổ hợp là không cần đến nhiều các công thức cồng kềnh hay phức tạp mà để giải chúng thì chủ yếu dựa vào tư duy nhạy bén là chính. Thêm vào đó là tính trừu tượng và rất dễ gây nhầm lẫn cho chúng ta. Chính vì lẽ đó mà ở nhiều nước trên thế giới họ đã đưa nội dung toán tổ hợp vào chương trình môn toán ngay từ rất sớm cho các lớp Trung học cơ sở. Còn ở nước ta thì mặc dù chưa được đưa vào sách giáo khoa chính thống cho học sinh Trung học cơ sở, nhưng loại toán này thường được sử dụng (như một thách thức đáng kể nhất) cho các kì thi học sinh giỏi và thi vào trường chuyên, lớp chọn. Chọn đề tài "Một số dạng bài toán tổ hợp" là chúng tôi đã lường trước được những khó khăn sẽ phải đối mặt. Luận văn này không có tham vọng trình bày một cách đầy đủ và hệ thống tất cả các dạng bài toán tổ hợp (vì chúng vốn rất đa dạng và phong phú) mà chỉ trình bày một số kĩ năng mang tính kinh nghiệm để giải quyết loại toán này. Những lý thuyết cơ bản đã được trình bày trong sách giáo khoa, chúng tôi không nêu lại mà chỉ trình bày một số công thức chưa thực sự là phổ biến, sau đó đi sâu vào các ví dụ để minh họa cho dạng toán và phương pháp mà chúng tôi muốn nói đến. Các ví dụ và bài toán được chúng tôi chọn lọc một cách cẩn thận từ rất nhiều nguồn tham khảo khác nhau, cũng có một số ít trong đó là do chúng tôi tự đưa ra. Luận văn này gồm 5 chương. Tuy nhiên cũng cần phải nói thêm rằng mọi sự phân chia đều chỉ mang tính tương đối và do ý thức chủ quan của tác giả mà thôi bởi trong toán học thì không có gì là thực sự rõ ràng về danh giới giữa các phần, các phân môn khác nhau. Luận văn được hoàn thành dưới sự hướng dẫn tận tình của PGS. TS Nguyễn Vũ Lương, người thầy của tôi. Tôi xin được bày tỏ lòng biết ơn sâu sắc đến sự giúp đỡ to lớn đó. Những sai xót, khiếm iv Lời mở đầu khuyết là điều khó tránh khỏi và những lỗi đó chỉ là thuộc về cá nhân tác giả. Chúng tôi mong nhận được sự thông cảm và những lời nhận xét, góp ý từ phía các thầy, các bạn bè đồng nghiệp. Hà Nội, tháng 5 năm 2013 Nguyễn Việt Hùng Chương 1 Các bài toán về tập hợp 1.1 Một số ví dụ Ví dụ 1 (Công thức tính lực lượng của hợp các tập hợp). Với n tập hợp hữu hạn tùy ý A1 , A2 , . . . , An ta có đẳng thức |A1 ∪ A2 ∪ · · · ∪ An | = n X i=1 |Ai | − X 1≤i 1, kí hiệu φ(n) là số các số nguyên dương bé hơn n và nguyên tố cùng nhau với n. Chứng minh rằng φ(n) = n m  Y i=1 1 1− pi  , trong đó p1 , p2 , . . . , pm là tất cả các ước nguyên tố phân biệt của n. LỜI GIẢI. Kí hiệu S = {1, 2, . . . , n}. Ta đếm xem trong tập S có bao nhiêu số chia hết cho ít nhất một trong các số p1 , p2 , . . . , pm . Gọi Ai = {k ∈ S| k chia hết cho pi } (i = 1, 2, . . . , m). Khi đó A1 ∪ A2 ∪ · · · ∪ Am là tập hợp các số chia hết cho ít nhất một trong các số p1 , p2 , . . . , pm . Ta có |Ai1 ∩ Ai2 · · · ∩ Aik | = n . pi1 pi2 · · · pik Do đó theo công thức ở bài toán trên ta có m X X n n − + |A1 ∪ A2 ∪ · · · ∪ Am | = p p p i i j 1≤i |A|, 3 2 |C ∩ D| > |C|, 3 2 |B ∩ C| > |B|, 3 2 |D ∩ A| > |D|. 3 Xét tổng S = |A ∩ B| + |B ∩ C| + |C ∩ D| + |D ∩ A|. Ta có 2 S > (|A| + |B| + |C| + |D|). 3 Sử dụng tính chất |X| + |Y | = |X ∪ Y | + |X ∩ Y | ta suy ra 1 S > (S + |A ∪ B| + |B ∪ C| + |C ∪ D| + |D ∪ A|) 3 hay 1 S > (|A ∪ B| + |B ∪ C| + |C ∪ D| + |D ∪ A|) 2 (1). 6 1.1. Một số ví dụ Giả sử không có học sinh nào đạt điểm giỏi ở cả bốn môn. Khi đó A ∩ C = ∅ hoặc B ∩ D = ∅. Không mất tính tổng quát ta có thể giả sử A ∩ C = ∅. Khi đó (A ∩ B) ∩ (B ∩ C) = (A ∩ C) ∩ B = ∅, (C ∩ D) ∩ (D ∩ A) = (A ∩ C) ∩ D = ∅. Mặt khác (A ∩ B) ∪ (B ∩ C) ⊂ B, (C ∩ D) ∪ (D ∩ A) ⊂ D. Do đó |A ∩ B| + |B ∩ C| ≤ |B|, |C ∩ D| + |D ∩ A| ≤ |D|. Suy ra S ≤ |B| + |D|. Lại có 1 |B| + |D| ≤ (|A ∪ B| + |B ∪ C| + |C ∪ D| + |D ∪ A|). 2 Suy ra 1 S ≤ (|A ∪ B| + |B ∪ C| + |C ∪ D| + |D ∪ A|), 2 nhưng điều này mâu thuẫn với (1). Chứng tỏ điều giả sử không thể xảy ra. Ví dụ 7. Cho tập S = {1, 2, 3, . . . , n}. Có bao nhiêu bộ sắp thứ tự (a, b, c) thỏa mãn a ≥ b ≥ c và a, b, c ∈ S. LỜI GIẢI. Gọi A = {(a, b, c)| a ≥ b ≥ c và a, b, c ∈ S}. Ta có A= n [ Ai , Ai = i [ Ai,j j=1 i=1 trong đó Ai,j = {(i, j, k)| 1 ≤ k ≤ j}. Rõ ràng các tập Ai đôi một rời nhau và các tập Ai,j cũng thế. Dễ thấy |Ai,j | = j. Do đó |Ai | = i X j=1 |Ai,j | = i X j=1 j= i(i + 1) . 2 7 1.1. Một số ví dụ |A| = n X i=1 |Ai | = n X i(i + 1) i=1 2 = n(n + 1)(n + 2) . 6 Ví dụ 8. Cho tập hợp S ⊂ R thỏa mãn các tính chất sau a) Z ⊂ S, b) √ √ 2 + 3 ∈ S, c) ∀x, y ∈ S : x + y ∈ S, xy ∈ S. 1 √ ∈ S. Chứng minh rằng √ 2+ 3 LỜI GIẢI. Từ tính chất thứ hai suy ra √ √ √ √ ( 2 + 3)2 = 5 + 2 6 ∈ S ⇒ 2 6 ∈ S. Do đó Mà √ √ √ √ √ 2 6( 2 + 3) = 4 3 + 6 2 ∈ S. √ Vậy √ 3− 1 √ ∈ S. 2+ 3 √ √ √ √ √ 2 = 5( 2 + 3) − (4 3 + 6 2) ∈ S. Ví dụ 9 (Toán học tuổi trẻ). Cho ba số nguyên tố p1 < p2 < p3 . Gọi A = {n ∈ N | 1 ≤ n ≤ p1 p2 p3 , n không chia hết cho pi , i = 1, 2, 3}. Chứng minh rằng |A| ≥ 8. Đẳng thức xảy ra khi nào? LỜI GIẢI. Gọi Ai = {n ∈ N | 1 ≤ n ≤ p1 p2 p3 , n chia hết cho pi }, i = 1, 2, 3. Dễ dàng tính được |A1 | = p2 p3 , |A2 | = p1 p3 , |A3 | = p1 p2 , |A1 ∩ A2 | = p3 , |A2 ∩ A3 | = p1 , |A3 ∩ A1 | = p2 , |A1 ∩ A2 ∩ A3 | = 1. 8 1.1. Một số ví dụ Do đó |A1 ∪ A2 ∪ A3 | = p1 p2 + p2 p3 + p3 p1 − p1 − p2 − p3 + 1. Suy ra |A| = p1 p2 p3 − |A1 ∪ A2 ∪ A3 | = (p1 − 1)(p2 − 1)(p3 − 1). Nhưng do p1 ≥ 2, p2 ≥ 3, p3 ≥ 5 nên ta có |A| ≥ 8. Đẳng thức xảy ra khi p1 , p2 , p3 là ba số nguyên tố đầu tiên. Nhận xét 2. Nếu sử dụng kiến thức về φ− hàm Euler thì rất đơn giản ta có |A| = φ(p1p2 p3 ) = φ(p1 )φ(p2)φ(p3 ) = (p1 − 1)(p2 − 1)(p3 − 1). Ví dụ 10. Tập hợp A có số phần tử gấp đôi số phần tử của tập hợp B, tập hợp B lớn hơn tập hợp C. Số các tập con của A nhiều hơn số các tập con của B là x. Số các tập con của B nhiều hơn số các tập con của C là 15. Hãy tính x. LỜI GIẢI. Giả sử |B| = n. Thế thì |A| = 2n. Số các tập con của B là 2n , số các tập con của A là 22n . Theo giả thiết ta có 22n − 2n = x (1) Đặt |C| = m (m < n), theo giả thiết ta lại có 2n − 2m = 15 (2) Từ (2) suy ra m = 0 vì nếu ngược lại (tức là m ≥ 1) thì vế trái là một số chẵn còn 15 lại là số lẻ. Do đó n = 4. Thay vào (1) ta tìm được x = 240. Ví dụ 11 (Toán học tuổi trẻ). Cho X là tập con của tập {1, 2, . . . , 2010} thỏa mãn đồng thời các điều kiện sau (i) |X| = 62, (ii) Với mọi x ∈ X đều tồn tại a, b ∈ X ∩ {0, 2011} (a và b đều khác x) sao a+b cho x = . 2 9 1.1. Một số ví dụ Chứng minh rằng có hai phần tử x, y của X sao cho |x − y| ≥ 11 và x+y ∈ / X. 2 LỜI GIẢI. Giả sử X có 62 phần tử đã được sắp thứ tự x1 < x2 < · · · < x62 . Ta chứng minh bằng phương pháp phản chứng. Giả sử không tồn tại x, y ∈ X x+y sao cho |x − y| ≥ 11 và ∈ / X. Ta sẽ chỉ ra các phần tử của X đều cùng 2 tình chẵn lẻ. Thật vậy, vì X ⊂ {1, 2, . . . , 2010} nên xi+1 ≥ xi + 1 (i = 1, 61). Do đó x62 − xk ≥ 11(k = 1, 51). Suy ra xk cùng tính chẵn lẻ với x62 , vì nếu không như xk + x62 ∈ X, trái với giả thiết. vậy, tức tồn tại xk khác tính chẵn lẻ với x62 thì 2 Lập luận tương tự ta thấy xl (l = 12, 62) cùng tính chẵn lẻ với x1 . Từ đó suy ra x1 , x2 , . . . , x6 2 cùng tính chẵn lẻ. Tiếp theo với giả thiết (ii) của bài toán thì a+b . Vì x62 > xi (i = 1, 61) tồn tại a, b ∈ X ∩ {0, 2011}, (a 6= b) sao cho x62 = 2 xp + 2011 kéo theo xp là một số lẻ. nên tồn tại xp (p = 1, 61) sao cho x62 = 2 Tương tự do xi > x1 (i = 2, 61) nên tồn tại xp với q ∈ 2, 3, . . . , 61 sao cho xq + 0 , kéo theo xq là một số chẵn. Như vậy xp và xq là hai phần tử của x1 = 2 X khác tính chẵn lẻ, trái với kết quả khẳng định ở trên, tức điều giả sử là sai. x+y ∈ / X. Kết luận: có hai phần tử x, y ∈ X sao cho |x − y| ≥ 11 và 2 Nhận xét 3. (i) Có thể thay |x| = 33. (ii) Bài toán tổng quát: Cho X ⊂ {1, 2, . . . , n}, |X| = k (k ≥ 2, k ∈ N). k x+y Chứng minh rằng tồn tại x, y ∈ X sao cho |x−y| ≥ ∈ / X. −1 và 2 2 Ví dụ 12 (Toán học tuổi trẻ). Tìm tất cả các tập hữu hạn A ⊂ N∗ sao cho P P 2 tồn tại tập hữu hạn B ⊂ N∗ thỏa mãn A ⊂ B và x= x. x∈B x∈A LỜI GIẢI. Gọi m là số lớn nhất trong A. Ta xét ba trường hợp • m = 1. Khi đó A = {1}. Ta chọn B = {1} yêu cầu bài toán được thỏa mãn. • m = 2. Trong trường hợp này ta có A = {2} hoặc A = {1, 2}. P 2 Nếu A = {2} thì x = 4. Như thế nếu tồn tại tập B thỏa mãn các x∈A P 2 điều kiện của bài toán thì x = 4 − 2 = 2. Từ đó B\A = {2}, mâu x∈B\ thuẫn, vì 2 ∈ A. 10 1.2. Bài tập đề nghị Nếu A = {1, 2} thì tương tự như trên ta cũng chứng minh được rằng không tồn tại tập B thỏa mãn các điều kiện của bài toán. • m > 2. Xét số y = P (x2 − x). Ta có y ≥ m2 − m = m(m − 1) ≥ 2m > m. x∈A P P P 2 Như thế y ∈ / A. Xét tập B = A ∪ {y}. Ta có x= x+y = x. Do đó tập B thỏa mãn yêu cầu bài toán. x∈B x∈A x∈A Vậy tất cả các tập A thỏa mãn bài toán là A = {1} hoặc A là tập hữu hạn tùy ý mà phần tử lớn nhất của nó lớn hơn 2. 1.2 Bài tập đề nghị Bài 1. Cho A là tập con gồm 90 phần tử của {1, 2, . . . , 100} và S là tổng các phần tử của A. Tìm số các giá trị có thể có của S. Bài 2. Cho tập hợp S = {a1 , a2 , . . . , a12 }, ở đó tất cả 12 phần từ đều khác nhau. Chúng ta sẽ tạo ra những tập hợp con của S. Chỉ có một ràng buộc là chỉ số dưới của mỗi phần tử trong mỗi tập con được tạo thành phải là bội nguyên của chỉ số dưới nhỏ nhất có trong tập hợp đó. Ví dụ {a2 , a4 , a8 } là một tập hợp được chấp nhận, tập {a6 } cũng vậy. Có bao nhiêu tập hợp như thế được tạo thành? Bài 3 (Toán học tuổi trẻ). Cho số nguyên dương n. Tính số các số nguyên dương không lớn hơn n(n+1)(n+2) mà không chia hết cho các số n, n+1, n+2. . HD. Kí hiệu S = {1, 2, . . . , n(n + 1)(n + 2)}, A1 = {k ∈ S| k .. n}, A2 = {k ∈ . . S| k .. n + 1}, A3 = {k ∈ S| k .. n + 2}. Số cần tìm là  n3 − n nếu n lẻ, |S| − |A1 ∪ A2 ∪ A3 | =  n3 nếu n chẵn. . Bài 4. Xét tập hợp X = {1, 2, . . . , 2012}. Đặt A = {x ∈ X| x − 2 | .. 29}. a) Tính |A|. b) Tìm số tập con B của X sao cho B ∩ A 6= ∅. 11 1.2. Bài tập đề nghị HD. b) Kí hiệu P (X) là họ tất cả các tập con của X. M = {B ⊂ X| B ∩A 6= ∅}. Khi đó P (X) \ M = {B ⊂ X| B ∩ A = ∅} = {B ⊂ X \ A}. Nghĩa là P (X) \ M = P (X \ A). Do đó |M| = |P (X)| − |P (X \ A)| = 22012 − 21942 . Bài 5. Một hộp đựng 9 thẻ được đánh số từ 1 đến 9. Hỏi phải rút ra ít nhất bao nhiêu thẻ để xác suất có ít nhất một thẻ ghi số chia hết cho 4 không nhỏ 5 hơn . 6 Bài 6 (Toán học tuổi trẻ). Cho 167 tập hợp A1 , A2 , . . . , A167 thỏa mãn các điều kiện (i) 167 P i=1 |Ai | = 2004, (ii) |Aj | = |Ai |.|Ai ∩ Aj | ∀i 6= j.    167 S   Tính  Ai  . i=1 Chương 2 Các bài toán về phép đếm 2.1 Tóm tắt lý thuyết Hoán vị lặp Số hoán vị thực sự khác nhau (tức phân biệt được) của một tập hợp gồm n phần tử, trong đó có n1 phần tử loại 1, n2 phần tử loại 2, . . . , nk phần tử loại k (các phần tử cùng loại giống hệt nhau, n1 + n2 + · · · + nk = n), gọi là số hoán vị lặp của n phần tử. Số hoán vị lặp của n phần tử như thế được kí hiệu là Pn (n1 , n2 , . . . , nk ) và được tính bởi công thức Pn (n1 , n2 , . . . , nk ) = n! . n1 !n2 ! . . . nk ! Chứng minh. Trong Pn (n1 , n2 , . . . , nk ) cách hoán vị thực sự khác nhau thì ứng với mỗi cách hoán vị ấy ta có thể tạo ra n1 !n2 ! . . . nk ! cách hoán vị nếu như tất cả n phần tử được coi là khác nhau. Nghĩa là ta có Pn (n1 , n2 , . . . , nk ).n1 !n2 ! . . . nk ! = n! Từ đó suy ra công thức tính Pn (n1 , n2 , . . . , nk ) như trên. Hoán vị vòng quanh Số cách xếp n đối tượng khác nhau theo một vòng tròn, trong đó hai cách xếp khác nhau bởi một phép quay (tức là hai cách xếp khác nhau về vị trí nhưng có cùng thứ tự đối với n đối tượng) được coi là một, gọi là số hoán vị 12 13 2.1. Tóm tắt lý thuyết vòng quanh của n phần tử khác nhau. Số hoán vị vòng quanh của n phần tử khác nhau kí hiệu là Qn và được tính bởi công thức Qn = (n − 1)!. Chứng minh. Ta có thể định trước một vị trí cho một đối tượng bất kì trong chúng, sau đó tính số cách xếp vị trí cho n − 1 đối tượng còn lại. Do đó số cách xếp sẽ là Qn = (n − 1)!. Chỉnh hợp lặp Một chỉnh hợp lặp chập k của n phần tử là một dãy có thứ tự gồm k phần tử, trong đó mỗi phần tử có thể lặp lại nhiều lần. Số chỉnh hợp lặp chập k của n phần tử kí hiệu là Akn và được tính bởi công thức Ank = nk . Chứng minh công thức này rất dễ nên ta bỏ qua. Tổ hợp lặp Một tổ hợp lặp chập k của n phần tử là một nhóm không kể thứ tự gồm k phần tử, trong đó mỗi phần tử có thể lặp lại nhiều lần. Số tổ hợp lặp chập k của n phần tử kí hiệu là Ckn và được tính bởi công thức Ckn = Ckn+k−1 . Chứng minh. Một tổ hợp lặp chập k của n phần tử tương ứng với một nhóm X1 , X2 , . . . , Xn trong đó phần tử Xi (i = 1, n) xuất hiện với tần xuất xi (0 ≤ xi ≤ k) lần và x1 + x2 + · · · + xn = k (∗) Như vậy số tổ hợp chập k của n phần tử chính bằng số nghiệm nguyên không âm của phương trình (∗). Sau này (trong phần các bài toán sử dụng song ánh) ta sẽ thấy rằng số nghiệm nguyên không âm của (∗) bằng Ckn = Ckn+k−1 . 14 2.2. Một số ví dụ Nhận xét 4. Khác với Ckn , Ckn không cần có điều kiện k ≤ n. 2.2 Một số ví dụ Ví dụ 13. Tổ một có 10 người, tổ hai có 12 người và tổ ba có 15 người. Hỏi có bao nhiêu cách chọn ra một nhóm gồm 10 người trong đó số người của tổ một không ít hơn 2, số người của tổ hai cũng không ít hơn 2 còn số người của tổ ba không vượt quá 3. 2 LỜI GIẢI. Trước hết ta lấy 2 người từ tổ một thì có C10 cách và cũng lấy 2 2 người từ tổ hai thì có C12 cách. Tiếp theo từ tổ ba ta lấy ra k (0 ≤ k ≤ 3) k người thì có C15 cách. Lúc này số người còn lại của tổ một và tổ hai ta đem 6−k gộp lại thành một nhóm 18 người. Từ nhóm này lấy ra 6 − k người thì có C18 . 6−k 2 2 k Theo quy tắc nhân, số cách chọn ra 10 người là C10 C12 C15 C18 . Cho k chạy từ 0 tới 3 và lấy tổng ta thu được số cách chọn thỏa mãn yêu cầu của đề bài là 2 2 0 6 2 2 1 5 2 2 2 4 2 2 3 3 C10 C12 C15 C18 + C10 C12 C15 C18 + C10 C12 C15 C18 + C10 C12 C15 C18 Ví dụ 14. Giả sử số nguyên dương n có phân tích ra thừa số nguyên tố là n = pn1 1 pn2 2 · · · pnk k . Ta dùng kí hiệu τn để chỉ số ước nguyên dương của n. Chứng minh rằng τn = (n1 + 1)(n2 + 1) · · · (nk + 1). mk 1 m2 LỜI GIẢI. Mọi ước nguyên dương của n đều có dạng pm 1 p2 · · · pk , trong đó m1 , m2 , . . . , mk là các số nguyên không âm và 0 ≤ m1 ≤ n1 , 0 ≤ m2 ≤ n2 , . . . , 0 ≤ mk ≤ nk . Như vậy, số ước nguyên dương của n đúng bằng số cách chọn bộ (m1 , m2 , . . . , mk ) thỏa mãn những điều kiện trên. Vì mi (i = 1, 2, . . . , k) có ni + 1 cách chọn nên số ước nguyên dương của n chính là τn = (n1 + 1)(n2 + 1) · · · (nk + 1).