ĐẠi học quốc gia hà NỘI
CHƯƠNG 2 - MỘT SỐ BÀI TOÁN TỔ HỢP CƠ BẢN
tải về 0.86 Mb.
|
- Điều hướng trang này:
- 2.1 Một số bài toán đếm không lặp
- 2.1.1 Bài toán lập số
- 2.1.2 Bài toán chọn vật, chọn người, sắp xếp.
- 2.1.3 Bài toán tương tự
CHƯƠNG 2 - MỘT SỐ BÀI TOÁN TỔ HỢP CƠ BẢNChương 1 đă tŕnh bày lư thuyết cơ bản của toán tổ hợp. Dựa trên cơ sở lư thuyết đó trong chương này khóa luận sẽ tập trung tŕnh bày một số bài toán tổ hợp cơ bản, phù hợp với học sinh THPT khi tham gia các ḱ thi tốt nghiệp, cao đẳng, đại học.
Trong các bài toán về phép đếm không lặp, mỗi phần tử cần đếm chỉ có thể xuất hiện tối đa một lần. Để giải các bài toán đếm không lặp người ta sử dụng hai quy tắc chính của phép đếm là quy tắc cộng và quy tắc nhân, cũng như sử dụng hai phương pháp đếm trực tiếp hoặc đếm gián tiếp .
Bài 1: Cho tập hợp các chữ số . Từ tập hợp có thể lập được bao nhiêu số chẵn có 6 chữ số khác nhau từng đôi một. Giải:
Gọi số cần lập là = , . V́ là số chẵn nên có 4 cách chọn. C̣n là một bộ phân biệt có thứ tự được chọn từ X do đó nó là một chỉnh hợp chập 5 của 8 (Trừ đi số a6 đă chọn). Có cách chọn. Vậy có số thỏa măn bài toán.
Giải: Gọi số cần lập là = , , . V́ là số chẵn nên . Trường hợp 1: Nếu th́ có 1 cách chọn. Khi đó là một bộ phân biệt có thứ tự được chọn từ X\{0} do đó nó là một chỉnh hợp chập 4 của 7. Có cách chọn. Vậy có =840 số thỏa măn bài toán. Trường hợp 2: Nếu được chọn từ {2, 4, 6} th́ có 3 cách chọn.
Vậy có 3.6. =2160 số thỏa măn bài toán. Vậy số các số chẵn gồm 5 chữ số phân biệt h́nh thành từ là: 840+2160=3000 số. b) V́ là số tiến nên và do nên . Mỗi cách chọn ra 5 chữ số th́ chỉ có 1 cách sắp xếp từ nhỏ đến lớn. Vậy số các số cần t́m là số cách chọn ra 5 chữ số từ tập . Vậy có =21 số thỏa măn điều kiện.
Giải:
Ta “dán” hai chữ số 2 và 3 thành một chữ số kép. Có hai cách dán 23 hoặc 32. Bài toán trở thành: “Từ năm chữ số thuộc B={ số kép} có thể lập được bao nhiêu số tự nhiên có năm chữ số khác nhau” Gọi số có năm chữ số được lập từ B là = , , . được chọn từ tập nên có 4 cách chọn. là một bộ phân biệt thứ tự được chọn từ do đó nó là một hoán vị của 4. Có 4! cách chọn. Vậy có 2.4.4 ! = 192 số thỏa măn bài toán. Bài 4: Từ tập có thể lập được bao nhiêu số có 6 chữ số sao cho mỗi chữ số xuất hiện nhiều nhất một lần. Tính tổng tất cả các số đó. Giải:
Xét trường hợp các số lập được từ có 6 chữ số (cả trường hợp số 0 đứng đầu). Có số. Ta thấy các số trong tập đều xuất hiện 120 lần trên các hàng trăm ngh́n, hàng chục ngh́n, hàng ngh́n, hàng trăm hàng chục và hàng đơn vị. Vậy tổng tất cả các số lập được trong trường hợp này là: Xét trường hợp số 0 đứng đầu , . Có = 5!= 120 số. Ta thấy các số 1, 2, 3, 4, 5 đều xuất hiện 24 lần trên các hàng chục ngh́n, hàng ngh́n, hàng trăm hàng chục và hàng đơn vị. Vậy tổng các số lập được trong trường hợp này là:
Tổng các số lập được có 6 chữ số là: số. Tổng tất cả các số đó là:
Giải:
Gọi số cần t́m là: , . Trường hợp 1: Số có dạng ( ). có thể nhận 3 giá trị 5, 7, 9 nên có 3 cách chọn. là một bộ 4 số có thứ tự lập từ . Có cách chọn bộ 4 số có kể thứ tự. Vậy có 3. số thỏa măn bài toán. Trường hợp 2: Số có dạng . là một bộ 5 phần tử từ và có kể thứ tự các phần tử. Có số. Trường hợp 3: số có dạng với .
Có số. Vậy có số thỏa măn bài toán.
Giải:
Gọi số cần t́m là: , . Ta có . Vậy tổng của ba chữ số đầu là 10. Dễ thấy . Vậy có 3 cách chọn 3 nhóm 3 chữ số đầu (1,3,6 hoặc 1,4,5 hoặc 2,3,5). Với 1 cách chọn nhóm 3 chữ số th́ có 3! cách để lập ra số . Với 3 số c̣n lại th́ có 3! cách để lập ra số . Vậy có 3.3!.3!=108 số cần t́m.
Giải:
Gọi số cần t́m là: , . Theo bài ra . Ta có . Vậy có hai cách chọn nhóm 3 số để tổng các chữ số hàng chục, hàng trăm, hàng ngh́n bằng 8. Với mỗi nhóm có 3 ! = 6 cách lập ra số . Với 3 chữ số c̣n lại là 1 bộ số có thứ tự được chọn từ tập . Có cách. Vậy có số thỏa măn bài toán. Bài 8: Từ tập có thể lập được bao nhiêu số tự nhiên gồm 5 chữ số khác nhau và nhất thiết phải có hai chữ số 1 và 5. Giải:
Trong 5 chữ số th́ có 2 chữ số là 1 và 5. Ta chỉ cần chọn ra ba số thuộc tập hợp . Số cách chọn là . Với 5 số được chọn ra có 5! cách thành lập số thỏa măn. Vậy có
Giải:
V́ có 3 số lẻ nên có 6 ‘số kép’ sau 13, 31, 15, 51, 35, 53. Bài toán trở thành có bao nhiêu số chẵn có 4 chữ số khác nhau được lập từ tập { số kép}. Gọi lần lượt là tập hợp các số chẵn có 4 chữ số khác nhau được lập từ tập trong đó ‘ số kép’ đứng ở vị trí thứ nhất, thứ hai, thứ ba. Trường hợp 1 : số kép đứng ở vị trí thứ nhất. Ba chữ số c̣n lại được chọn từ tập : Có cách chọn Trường hợp 2 : số kép đứng ở vị trí thứ hai hoặc thứ ba . Số đứng đầu được chọn từ tập : có 3 cách chọn Hai chữ số c̣n lại được chọn từ tập \{chữ số đầu}: Có cách chọn. Vậy Vậy có số thỏa măn bài toán. Bài 10: Số 360 có bao nhiêu ước tự nhiên ? Giải :
Phân tích 360 ra thừa số nguyên tố : Số d là ước của 360 phải có dạng với Vậy theo quy tắc nhân, ta có ước tự nhiên của 360.
Để t́m số các ước của số A ta thực hiện theo các bước sau : Bước 1 : Phân tích A ra thành thừa số nguyên tố. với và đôi một khác nhau. Bước 2 : Số d là ước của A phải có dạng
Bước 3 : Số các ước tự nhiên của A là . Bài 11: Có bao nhiêu số nguyên dương là ước của ít nhất một trong hai số 5400 và 18000? Giải :
Đặt ; . Yêu cầu bài toán là t́m Trước hết ta t́m Ta có
Vận dụng kết quả tổng quát của bài 10 ta có
Mặt khác tập hợp là tập các ước nguyên dương của 5400 và 18000, v́ thế cũng là tập hợp của các ước dương của ước chung lớn nhất của 5400 và 18000. Mà . Vậy ta có . Cuối cùng ta có
Giải :
Đặt ; ; Yêu cầu bài toán là t́m Ta có
Mặt khác ta thấy là tập các số nguyên trong S chia hết cho cả 3 và 5 nên nó phải chia hết cho BCNN của 3 và 5, mà nên . Vậy ta có
Bài 13: Có 12 cây giống 3 loại : xoài, mít, ổi trong đó 6 xoài, 4 mít, 2 ổi. Muốn chọn ra 6 cây giống đă trồng. Hỏi có bao nhiêu cách :
Giải :
Chọn 2 cây mít có cách. Chọn 2 cây ổi có cách. Vậy theo quy tắc nhân có 15.6.1=90 cách
Gọi B là tập hợp cách chọn 6 cây không đủ 3 loại. Cách chọn chỉ có xoài: 1 cách chọn. Cách chọn chỉ có xoài và mít: cách chọn. Cách chọn chỉ có xoài và ổi: cách chọn. Cách chọn chỉ có mít và ổi: 1 cách chọn. Do đó Vậy số cách chọn có đủ các loại là: cách. Bài 14: Một thầy giáo có 20 cuốn sách đôi một khác nhau. Trong đó có 5 cuốn sách văn học, 4 cuốn sách âm nhạc và 3 cuốn sách hội họa. Ông muốn lấy ra 6 cuốn và đem tặng cho 6 học sinh mỗi em một cuốn sao cho sau khi tặng sách xong, mỗi một trong ba thể loại văn học, âm nhạc và hội họa đều c̣n lại ít nhất một cuốn. Hỏi có bao nhiêu cách tặng ? Giải:
Có cách chọn 6 cuốn sách bất kỳ trong 12 cuốn trong đó. Có cách chọn 6 cuốn có 5 cuốn văn học. Có cách chọn 6 cuốn có 4 cuốn âm nhạc. Có cách chọn 6 cuốn có 3 cuốn hội họa. Vậy có ( + + )=805 cách chọn thỏa măn điều kiện. Với mỗi cách chọn ta có 6! Cách tặng. Vậy số cách tặng thỏa măn là 805.6!=579600 cách.
Giải: a. Số cách chọn 4 học sinh từ 12 học sinh là . Số cách chọn 4 học sinh mà mỗi khối lớp có ít nhất 1 em được tính như sau: Khối lớp 10 có 2 học sinh, các khối lớp 11, 12 có 1 học sinh có =120 cách. Khối lớp 11 có 2 học sinh, các khối lớp 10, 12 có 1 học sinh có =90 cách. Khối lớp 12 có 2 học sinh, các khối lớp 10, 11 có 1 học sinh có =60 cách. Vậy số cách chọn 4 học sinh mà mỗi khối lớp có ít nhất 1 học sinh là 120+90+60=270. Vậy số cách chọn thỏa măn là 495-270=225. b. Ta chọn 6 học sinh thỏa măn đề bài vào tổ 1, 6 học sinh c̣n lại tạo thành tổ 2. Có cách chọn tổ 1 trong đó có 2 học sinh khối lớp 10, 3 học sinh khối lớp 11, 1 học sinh khối lớp 12. Có cách chọn tổ 1 trong đó có 2 học sinh khối lớp 10, 2 học sinh khối lớp 11, 2 học sinh khối lớp 12. Có cách chọn tổ 1 trong đó có 3 học sinh khối lớp 10, 2 học sinh khối lớp 11, 1 học sinh khối lớp 12. Có cách chọn tổ 1 trong đó có 3 học sinh khối lớp 10, 1 học sinh khối lớp 11, 2 học sinh khối lớp 12. Vậy có + + + = 600 cách chia tổ thỏa măn đề bài. Bài 16: Có nam, nữ. Có bao nhiêu cách sắp xếp sao cho: a. người ngồi quanh một bàn tṛn. b. người ngồi vào hai dăy ghế đối diện sao cho nam nữ ngồi đối diện. Giải:
a. Người thứ nhất có 1 cách chọn chỗ ngồi v́ chỗ ngồi nào cũng không phân biệt so với bàn tṛn. Sau khi có chuẩn của người thứ nhất th́ người c̣n lại có cách xếp chỗ ngồi. Vậy có Cách. b. Xếp nam vào 1 dăy ghế có cách. Xếp nữ vào 1 dăy ghế có cách. Đổi chỗ cặp nam nữ đối diện có 2.2…2= cách. Vậy có cách xếp nam nữ ngồi đối diện nhau.
Giải:
Có cách chọn 4 viên chỉ có màu vàng. Có cách chọn 4 viên không có màu vàng. Có cách chọn 4 viên không có màu trắng. Có cách chọn 4 viên không có màu đỏ. Trong cách chọn 4 viên bi không có bi trắng có chứa cách chọn 4 viên chỉ có màu vàng. Trong cách chọn 4 viên không có bi đỏ có chứa cách chọn 4 viên chỉ có màu vàng. Vậy có + + + - - =105 cách chọn.
Giải:
Gọi A là tập hợp cách chọn đề có 3 câu dễ, 1 câu khó, 1 câu trung b́nh. Gọi B là tập hợp cách chọn đề có 2 câu dễ, 2 câu khó, 1 câu trung b́nh. Gọi C là tập hợp cách chọn đề có 2 câu dễ, 1 câu khó, 2 câu trung b́nh. Gọi D là tập hợp cách chọn thỏa măn yêu cầu bài ra. Ta có Ngoài ra A, B, C đôi một không giao nhau. Theo quy tắc cộng ta có : . Theo quy tắc nhân ta có : Thay vào (1) ta có . Vậy có 56875 cách chọn đề kiểm tra thỏa măn bài toán.
Giải:
Đầu tiên ta chọn 4 nam và 1 nữ cho tỉnh thứ nhất. Theo quy tắc nhân số cách chọn là : Sau đó chọn 4 nam và 1 nữ cho tỉnh thứ 2. 4 nam được chọn trong 8 nam c̣n lại và 1 nữ sẽ được chọn trong 2 nữ c̣n lại. Theo quy tắc nhân số cách chọn là :
Số c̣n lại thuộc tỉnh thứ 3. Vậy số cách phân công là
Giải:
Gọi A là tập hợp mọi cách chọn 4 học sinh trong 12 học sinh. Gọi B là tập hợp cách chọn không thỏa măn yêu cầu đề bài. Gọi C là tập hợp cách chọn thỏa măn yêu cầu đề bài. Ta có Theo quy tắc cộng ta có Dễ thấy Để tính , ta nhận thấy sẽ chọn 1 lớp có 2 học sinh, hai lớp c̣n lại mỗi lớp 1 học sinh. Theo quy tắc cộng và quy tắc nhân ta có
Thay vào (1) ta có . Vậy có 225 cách chọn.
Giải:
Ta có thể dùng 99 vách ngăn để ngăn 100 sản phẩm. Chọn 11 vách ngăn trong số 99 vách ngăn trên ta được một cách phân bố sản phẩm cho 12 cửa hàng thỏa măn bài toán. Vậy có cách phân bố Tổng quát: Số cách phân bố k sản phẩm cho n cửa hàng trong đó mỗi cửa hàng có ít nhất một sản phẩm là Bài 22: Một lớp học có 45 học sinh. Có bao nhiêu cách chọn nhóm 5 bạn vào ban cán sự của lớp sao cho có một bạn làm lớp trưởng. Giải:
Trước hết ta chọn 5 học sinh trong 45 học sinh của lớp. Có cách. Sau đó trong 5 học sinh này ta chọn một bạn làm lớp trưởng. Có 5 cách. Vậy có 5. cách chọn thỏa măn bài toán.
Giải:
Giả sử nhóm có k người (v́ phải luôn có một người làm trưởng nhóm). Trước hết ta chọn k người trong n người. Có cách. Sau đó trong k người này ta chọn một bạn làm trưởng nhóm. Có k cách. Do đó có cách chọn nhóm có k người trong đó luôn có một người làm nhóm trưởng. Vậy có cách chọn một nhóm người trong số n người sao cho có một người làm nhóm trưởng.
Giải:
Giả sử nhóm có k người (v́ phải luôn có một người làm nhóm trưởng , một người là nhóm phó). Trước hết ta chọn k người trong n người. Có cách. Sau đó trong k người này ta chọn một bạn làm nhóm trưởng . Có k cách. Trong k-1 người c̣n lại ta chọn một bạn làm nhóm phó. Có k-1 cách. Do đó có cách chọn nhóm có k người trong đó luôn có một người làm nhóm trưởng , một người là nhóm phó. Vậy có cách chọn một nhóm người trong số n người sao cho có một người làm nhóm trưởng , một người là nhóm phó. Bài 25 : ( Hoán vị ṿng quanh) a. Tính số hoán vị ṿng quanh của n phần tử khác nhau. b. Một hội nghị bàn tṛn có phái đoàn của các nước : Anh 3 người, Nga 5 người, Mỹ 2 người, Pháp 3 người, Trung Quốc 4 người. Hỏi có bao nhiêu cách sắp xếp chỗ ngồi cho mọi thành viên sao cho người cùng quốc tịnh th́ ngồi cạnh nhau. Giải :
Vậy số hoán vị ṿng quanh của n là
Như vậy có 24 cách sắp xếp các phái đoàn ngồi theo quốc gia ḿnh. Bây giờ ta xem có bao nhiêu cách sắp xếp chỗ ngồi cho nội bộ từng phái đoàn. Từ giả thiết ta có 3! Cách sắp xếp cho phái đoàn Anh. 5! Cách sắp xếp cho phái đoàn Nga. 2! Cách sắp xếp cho phái đoàn Mỹ. 3! Cách sắp xếp cho phái đoàn Pháp. 4! Cách sắp xếp cho phái đoàn Trung Quốc. Theo quy tắc nhân số cách sắp xếp cho hội nghị là cách sắp xếp. Chú ư : Ta có thể mở rộng phần 1 của bài 25 như sau : Số cách sắp xếp m số khác nhau từ tập hợp n số lên một đường tṛn bằng . Thật vậy Chọn m phần tử khác nhau trong n phần tử đă cho (không kể thứ tự sắp xếp). Số cách chọn là . Với m phần tử được chọn xếp m số đó lên đường tṛn . Theo hoán vị ṿng quanh số cách sắp xếp là Theo quy tắc nhân số cách sắp xếp m số khác nhau lên đường tṛn là Bài 26: ( Bài toán vui) Một cửa hàng có 10 lon nước giải khát đôi một khác nhau dùng để bày hàng. Người ta xếp các lon đó thành h́nh quả núi, số lon từ hàng dưới cùng đến hàng trên cùng lần lượt là 4, 3, 2, 1. Hàng ngày người ta đổi vị trí các lon cho nhau sao cho không có hai ngày bày như nhau. Hỏi bắt đầu từ ngày 1.1.2000 th́ có thể tiến hành đến ngày nào ? Giải :
Có 10 vị trí khác nhau, bày 10 lon nước giải khát đôi một khác nhau, vậy số cách bày là Vậy cần có 3628800 ngày để bày hết tất cả các cách. Do cứ 4 năm th́ có một năm nhuận, nên số ngày của chu ḱ 4 năm là ngày Ta thấy Ta lại lưu ư rằng những năm chia hết cho 400 không phải năm nhuận. như vậy không kể năm 2000, trong 2483. 4 năm có thêm 24 năm chia hết cho 4 mà không phải năm nhuận. Vậy ngày năm năm +66 ngày. Như vậy có thể bày tới ngày thứ 66 của năm 11936. Do năm này là năm nhuận nên . Vậy ngày cuối cùng có thể bày là mồng 6 tháng 3 năm 11936.
Bài 27: Có bao nhiêu số tự nhiên gồm 4 chữ số sao cho không có chữ số nào lặp lại quá 1 lần. Bài 28: Có bao nhiêu số tự nhiên gồm 5 chữ số và chữ số đứng sau bé hơn chữ số đứng trước. Bài 29: Có bao nhiêu số tự nhiên gồm 6 chữ số khác nhau là số lẻ và nhỏ hơn 600000. Bài 30: Có bao nhiêu số tự nhiên gồm 5 chữ số khác nhau là số chẵn và nhỏ hơn 25000. Bài 31: Từ được bao nhiêu số chẵn có 3 chữ số khác nhau và không lớn hơn 789. Bài 32: Có thể lập được bao nhiêu số tự nhiên có 5 chữ số khác nhau được lập từ tập sao cho một trong ba chữ số đầu tiên là 1. Bài 33: Có 20 học sinh (8 nữ trong đó có Lan, 12 nam trong đó có Nam và Tí ). a) Có bao nhiêu cách chọn ra một tổ 7 người trong đó có nhiều nhất 2 trong 3 bạn Tí, Nam và Lan. b) Có bao nhiêu cách xếp thành một hàng dọc sao cho Lan đứng đầu và các bạn nam luôn đứng cạnh nhau nhưng Tí và Nam không đứng cạnh nhau.
a) Có bao nhiêu cách lấy ra 3 quả cầu cùng màu, 3 quả cầu cùng số. b) Có bao nhiêu cách lấy ra 3 quả cầu khác màu, 3 quả cầu khác màu và khác số?
a) Bất kỳ hai học sinh ngồi cùng nhau hoặc đối diện nhau đều không cùng giới tính. b) Bất kỳ hai học sinh ngồi đối diện nhau đều không cùng giới tính.
|