Tìm số nghiệm nguyên không âm của phương trình x1+x2+x3+x4=16
|
Bài này có thể đưa về dạng toán đã biết trước là đếm số nghiệm nguyên không âm của phương trình x1+x2+x3+x4=30 với x1>=a,x2>=b,x3>=c <=> x+y+z+t=30-a-b-c=m với x=x1-a,y=x2-b,z=x3-c thì số nghiệm là C(m+3,3) { C là tổ hợp } (1) đặt F(a,b,c) tương ứng là kết quả của bài toán trên. Thì kết của của bài toán đề ra <=> F(0,0,0)-F(18,0,0)-F(0,11,0)-F(0,0,9)+F(18,11,0)+F(18,0,9)+F(0,11,9)-F(18,11,9) tính kết quả dựa trên công thức (1) thì kết quả bài toán = C(33,3)-C(33-18,3)-C(33-11,3)-C(33-9,3)+C(33-18-11,3)+C(33-18-9,3)+C(33-11-9,3) =1747
NGUYÊN LÝ BÙ TRỪBÀI 6 TRANG 44_1Có bao nhiêu hoán vị của các số tự nhiên 1, 2…10 màtrong đó 3 số 1, 2, 3 không đứng cạnh nhau theo thứtự tăng dần.GIẢI: Gọi |A| là tập các hoán vị của các số tự nhiên từ 1…10=> |A| =10!Gọi |A1| là tập các số tự nhiên gồm 3 số 1, 2, 3 gomthành một nhóm và theo thứ tự tăng dần, và các sốcòn lại 4…10. Như vậy |A1| là tập hoán vị của 8 số => |A1|=8!NGUYÊN LÝ BÙ TRỪBÀI 6 TRANG 44_2Gọi |A2| là tập các số tự nhiên trong đó 3 số 1,2, 3 không đứng cạnh nhau theo thứ tự tăngdần Theo nguyên lý bù trừ, ta thu được|A2| = 10! - 8! = 3588480 ( hoán vị )BÀI 7 TRANG 44, 45Hỏi phương trình x1 + x2 + x3 + x4 = 29 có bao nhiêu nghiệmnguyên không âm thỏa mãn x1 ≤ 3, x2 ≤ 12, x3 ≤ 5, x4 ≤ 10GIẢI: Theo giả thiết ta có x1 + x2 + x3 + x4 = 29(3 − x1 ) + (12 − x2 ) + (5 − x3 ) + (10 − x4 ) = 1 Đặt t1 = 3 − x1 , t2 = 12 − x2 , t3 = 5 − x3 , t4 = 10 − x4→¬=> t1 ≥ 0, t 2 ≥ 0, t3 ≥ 0, t4 ≥ 0 và t1 ≤ 3, t2 ≤ 12, t3 ≤ 5, t4 ≤ 10Điều kiện sau là hiển nhiên vớI các nghiệm của pt t1 + t2 + t3 + t4 = 1Bài toán trở về trường hợp bài toán chia tiềnSố nghiệm của phương trình tương ứng với số cách chia tiềnÁp dụng vào bai toán => số nghiệm là :cnk+−1k −1c14+−41−1= 4 ( nghiệm)BÀI 8 TRANG 45_1Một lớp có 50 học sinh làm bài kiểm tra gồm 3 câu hỏi.Biết rằng mỗi học sinh làm được ít nhất một câu, và sốhọc sinh làm được câu 1 là 40, câu 2 là 35, câu 3 là30. Chứng minh rằng số học sinh làm được 3 câukhông vượt quá 27.GIẢI: Gọi tập hợp số học sinh làm được số câu hỏi 1 là :|X1| Gọi tập hợp số học sinh làm được số câu hỏi 2 là :|X2| Gọi tập hợp số học sinh làm được số câu hỏi 3 là :|X3| Theo giả thiết ta có : |X1|=40 , |X2|=35,|X3|=30 vàBÀI 8 TRANG 45_2Theo nguyên lý của tập hợp ta có| X 1 ∪ X 2 ∪ X 3|= | X 1| + | X 2 | + | X 3| − | X 1 ∩ X 2 | − | X 2 ∩ X 3|− | X 1 ∩ X 3| + | X 1 ∩ X 2 ∩ X 3|Đặt | X 1 ∩X 2 ∩X 3 |=K=> 50 =105- | X 1 ∩ X 2 | − | X 1 ∩ X 3 | − | X 3 ∩ X 1| + KĐặt K1 =| X 1 ∩ X 2 | − | X 1 ∩ X 2 ∩ X 3 |≥ 0K 2 =| X 2 ∩ X 3 | − | X 1 ∩ X 2 ∩ X 3 |≥ 0K 3 =| X 3 ∩ X 1| − | X 1 ∩ X 2 ∩ X 3 |≥ 0BÀI 8 TRANG 45_3Do đó ta có : 50 = 105 - (3K+K1+K2+K3) + K=>2K ≤ 55 ( do K1+K2+K3 ≥ 0 ) => K ≤ 27Vậy số học sinh làm không quá được cả 3 câukhông quá 27( đpcm)
Toán rời rạc 2 counting
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (842.19 KB, 81 trang ) Học viện Công nghệ Bưu chính Viễn thông Bài tập 2 http://www.ptit.edu.vn Giới thiệu bài toán đếm Bài toán đếm o o Là bài toán đếm xem có bao nhiêu cấu hình tổ hợp có thể được tạo ra với những quy tắc đã nêu? Lời giải thường phụ thuộc vào một số tham số ban đầu và người ta cố gắng biều diễn những phụ thuộc này bằng những công thức toán học Nguyên tắc chung giải bài toán đếm o Để đếm các cấu hình đã cho, người ta tìm cách đưa về các cấu hình quen thuộc bằng cách thiếp lập một quan hệ 1-1 giữa chúng Ứng dụng của bài toán đếm trong khoa học máy tính o o 3 Ước lượng số phép toán thực hiện trong một giải thuật, chương trình máy tính Ước lượng độ phức tạp thời gian và không gian của giải thuật http://www.ptit.edu.vn Các phương pháp giải quyết bài toán đếm Sử dụng các nguyên lý đếm cơ bản: nguyên lý cộng, nguyên lý nhân, nguyên lý bù trừ Qui về các bài toán con: Phân tích lời giải bài toán đếm phức tạp thành những bài toán con. Trong đó, mỗi bài toán con có thể giải được bằng các nguyên lý đếm cơ bản Sử dụng hệ thức truy hồi: Xây dựng công thức tính số nghiệm tổng quát bất kỳ dựa vào biểu diễn các số hạng biết trước Phương pháp hàm sinh: Sử dụng hàm sinh của một dãy số để đếm các cấu hình tổ hợp 4 http://www.ptit.edu.vn Nội dung Giới thiệu bài toán Các nguyên lý đếm cơ bản Quy về bài toán con Hệ thức truy hồi Phương pháp hàm sinh Bài tập 5 http://www.ptit.edu.vn Nguyên lý cộng (nhắc lại) Nếu 𝐴 và 𝐵 là hai tập rời nhau thì 𝐴∪𝐵 = 𝐴 + 𝐵 Nếu *𝐴1 , 𝐴2 , … , 𝐴𝑘 + là một phân hoạch của tập hợp 𝑋 thì 𝑋 = 𝐴1 + 𝐴2 + ⋯ + 𝐴𝑘 Nếu có 𝐾 việc, việc thứ 𝑖 thực hiện bằng 𝑛𝑖 cách và thực hiện một cách tuần tự. Khi đó sẽ có 𝑛1 + 𝑛2 +. . + 𝑛𝐾 cách thực hiện một trong 𝐾 việc nêu trên. 6 http://www.ptit.edu.vn Ví dụ 1 Bài toán: Giả sử 𝑁, 𝑀 là hai số tự nhiên đã xác định giá trị. Hãy cho biết giá trị của 𝑆 sau khi thực hiện đoạn chương trình. 𝑆 = 0; for (𝑖 = 1; 𝑖 <= 𝑁; 𝑖 + +) 𝑆 + +; for (𝑗 = 1; 𝑗 <= 𝑀; 𝑗 + +) 𝑆 + +; 7 http://www.ptit.edu.vn Ví dụ 1 Bài toán: Giả sử 𝑁, 𝑀 là hai số tự nhiên đã xác định giá trị. Hãy cho biết giá trị của 𝑆 sau khi thực hiện đoạn chương trình. 𝑆 = 0; for (𝑖 = 1; 𝑖 <= 𝑁; 𝑖 + +) 𝑆 + +; for (𝑗 = 1; 𝑗 <= 𝑀; 𝑗 + +) 𝑆 + +; Lời giải: Gọi số phép toán thực hiện trong vòng lặp thứ nhất là 𝑇1 , số phép toán thực hiện trong vòng lặp thứ hai là 𝑇2 . Vì hai vòng lặp thực hiện độc lập nhau nên theo nguyên lý cộng, giá trị của 𝑆 = 𝑇1 + 𝑇2 = 𝑁 + 𝑀. 8 http://www.ptit.edu.vn Nguyên lý nhân (nhắc lại) Giả sử một nhiệm vụ nào đó được tách ra làm hai việc. Việc thứ nhất có thể thực hiện bằng 𝑛1 cách, việc thứ hai thực hiện bằng 𝑛2 cách sau khi việc thứ nhất đã được thực hiện. Khi đó, sẽ có 𝑛1𝑛2 cách thực hiện nhiệm vụ nêu trên. Nếu mỗi thành phần 𝑎𝑖 của bộ có thứ tự 𝑘 thành phần (𝑎1 , 𝑎2 , … , 𝑎𝑘 ) có 𝑛𝑖 khả năng chọn, thì số bộ được tạo ra sẽ là tích các khả năng 𝑛1 𝑛2 … 𝑛𝑘 Hệ quả: 9 o 𝐴1 × 𝐴2 × ⋯ × 𝐴𝑘 = 𝐴1 𝐴2 … 𝐴𝑘 o 𝐴𝑘 = |𝐴|𝑘 http://www.ptit.edu.vn Ví dụ 3 Bài toán: Giả sử 𝑛1, 𝑛2 là hai số nguyên dương đã xác định giá trị. Hãy cho biết giá trị của 𝑆 sau khi thực hiện đoạn chương trình dưới đây? int 𝑆 = 0; for (int 𝑖 = 1; 𝑖 <= 𝑛1; 𝑖 + +) for (int 𝑗 = 1; 𝑗 <= 𝑛2; 𝑗 + +) 𝑆 + +; 10 http://www.ptit.edu.vn Ví dụ 3 Bài toán: Giả sử 𝑛1, 𝑛2 là hai số nguyên dương đã xác định giá trị. Hãy cho biết giá trị của 𝑆 sau khi thực hiện đoạn chương trình dưới đây? int 𝑆 = 0; for (int 𝑖 = 1; 𝑖 <= 𝑛1; 𝑖 + +) for (int 𝑗 = 1; 𝑗 <= 𝑛2; 𝑗 + +) 𝑆 + +; Lời giải. Với mỗi giá trị của 𝑖 = 1,2, . . , 𝑛1 thì 𝑆 được cộng 𝑛2 đơn vị. Do vậy, theo nguyên lý nhân, sau 𝑛1 vòng lặp giá trị của 𝑆 = 𝑛1𝑛2. 11 http://www.ptit.edu.vn Ví dụ 4 Bài toán: có bao nhiêu tên biến trong ngôn ngữ lập trình C độ dài 8 chỉ chứa hai chữ cái a,b và bắt đầu bởi aaa hoặc bbb? 12 http://www.ptit.edu.vn Ví dụ 4 Bài toán: có bao nhiêu tên biến trong ngôn ngữ lập trình C độ dài 8 chỉ chứa hai chữ cái a,b và bắt đầu bởi aaa hoặc bbb? Lời giải: Tập các biến thỏa mãn đề bài được phân hoạch làm 2 tập: một tập gồm các biến bắt đầu bằng aaa, tập kia gồm các biến bắt đầu bằng bbb. Mỗi tên biến độ dài 8 bắt đầu bằng aaa (hoặc bbb) có thể được xây đựng như sau: o o o Chọn ký tự thứ 4, chọn ký tự thứ 5, …, chọn ký tự thứ 8. Mỗi ký tự có 2 cách chọn: a hoặc b Có tất cả 2 × 2 × 2 × 2 × 2 = 32 cách Toàn bộ có: 32 + 32 = 64 biến 13 http://www.ptit.edu.vn Hoán vị, chỉnh hợp, tổ hợp (nhắc lại) Số hoán vị của 𝑛 phần tử: 𝑛. 𝑛 − 1 … 2.1 = 𝑛! Số chỉnh hợp lặp chập 𝑘 của 𝑛 phần tử là 𝑛𝑘 số chỉnh hợp không lặp chập 𝑘 của 𝑛 phần tử là 𝑛! 𝑛 𝑛−1 … 𝑛−𝑘+1 = 𝑛−𝑘 ! Số tổ hợp chập 𝑘 của 𝑛 phần tử là 𝑛! 𝑘 𝐶𝑛 = 𝑘! 𝑛 − 𝑘 ! 14 http://www.ptit.edu.vn Ví dụ 5 Bài toán: Phương trình 𝑥1 + 𝑥2 + 𝑥3 = 11 có bao nhiêu nghiệm nguyên không âm? 15 http://www.ptit.edu.vn Ví dụ 5 Bài toán: Phương trình 𝑥1 + 𝑥2 + 𝑥3 = 11 có bao nhiêu nghiệm nguyên không âm? Lời giải: Số nghiệm nguyên không âm của phương trình bằng số cách chọn 11 phần tử từ 3 tập khác nhau. Ta biểu diễn 11 phần tử bằng 11 số 1 trên một đường thẳng. Sau đó sử dụng 2 số 0 để chia 11 phần tử này ra thành 3 nhóm. Số số 1 trong mỗi nhóm tương ứng số phần tử ta sẽ chọn từ tập tương ứng. Như vậy số nghiệm của phương trình chính là số cách chọn 11 vị trí để đánh số 1 trong một dãy 13 vị trí (để đánh 0 và 1). 11 𝐶13 16 13 × 12 = = 78 2 http://www.ptit.edu.vn Ví dụ 6 Bài toán: Phương trình 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑛 = 𝑘 có bao nhiêu nghiệm nguyên không âm? 17 http://www.ptit.edu.vn Ví dụ 6 Bài toán: Phương trình 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑛 = 𝑘 có bao nhiêu nghiệm nguyên không âm? Lời giải: Tương tự Ví dụ 5 ta sẽ có số nghiệm nguyên không âm của phương trình là: 𝑘 𝐶𝑛−1+𝑘 18 𝑛−1+𝑘 ! = 𝑘! 𝑛 − 1 ! http://www.ptit.edu.vn Ví dụ 7 Bài toán: Phương trình 𝑥1 + 𝑥2 + 𝑥3 = 11 có bao nhiêu nghiệm nguyên không âm thỏa mãn 𝑥1 1, 𝑥2 2, 𝑥3 3. 19 http://www.ptit.edu.vn Ví dụ 7 Bài toán: Phương trình 𝑥1 + 𝑥2 + 𝑥3 = 11 có bao nhiêu nghiệm nguyên không âm thỏa mãn 𝑥1 1, 𝑥2 2, 𝑥3 3. Lời giải: Phương trình tương đương: (𝑥1 −1) + (𝑥2 −2) + (𝑥3 −3) = 5 Đặt 𝑦1 = 𝑥1 − 1, 𝑦2 = 𝑥2 − 2, 𝑦3 = 𝑥3 − 3 Phương trình trở thành: 𝑦1 + 𝑦2 + 𝑦3 = 5 Theo Ví dụ 6, số nghiệm nguyên không âm là 7×6 5 5 𝐶3−1+5 = 𝐶7 = = 21 2 20 http://www.ptit.edu.vn Ví dụ 8 Bài toán: Phương trình 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑛 = 𝑘 có bao nhiêu nghiệm nguyên không âm thỏa mãn 𝑥1 ≥ 𝑚1 , … , 𝑥𝑛 ≥ 𝑚𝑛 ? 21 http://www.ptit.edu.vn Ví dụ 8 Bài toán: Phương trình 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑛 = 𝑘 có bao nhiêu nghiệm nguyên không âm thỏa mãn 𝑥1 ≥ 𝑚1 , … , 𝑥𝑛 ≥ 𝑚𝑛 ? Lời giải: Phương trình tương đương 𝑥1 − 𝑚1 + ⋯ + (𝑥𝑛 −𝑚𝑛 ) = 𝑘 −(𝑚1 + ⋯ + 𝑚𝑛 ) Đặt 𝑚 = 𝑘 −(𝑚1 + ⋯ + 𝑚𝑛 ) Bài toán quy về tìm số nghiệm nguyên không âm của phương trình: 𝑦1 + 𝑦2 + ⋯ + 𝑦𝑛 = 𝑚 𝑚 Theo Ví dụ 6: 𝐶𝑛−1+𝑚 22 http://www.ptit.edu.vn Ví dụ 9 Bài toán: Phương trình 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 + 𝑥6 = 24 có bao nhiêu nghiệm nguyên không âm thỏa mãn 1𝑥1 5, 3 𝑥2 7? Ví dụ 9 Bài toán: Phương trình 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 + 𝑥6 = 24 có bao nhiêu nghiệm nguyên không âm thỏa mãn 1𝑥1 5, 3 𝑥2 7? Lời giải: Gọi 𝑁1 , 𝑁2 , 𝑁3 , 𝑁4 là số các nghiệm nguyên không âm của phương trình (1), (2), (3), (4). x1 x 2 x3 x 4 x5 x 6 24 x1 1, x 2 3 x1 x 2 x3 x 4 x5 x 6 24 x1 6, x 2 3; x1 x 2 x3 x 4 x5 x 6 24 x1 1, x 2 8; x1 x 2 x3 x 4 x5 x 6 24 x1 6, x 2 8; (1) (2) (3) (4) Ví dụ 9 Theo Ví dụ 8 ta có: 20 20 𝑁1 = 𝐶6−1+20 = 𝐶25 = 53130 15 15 𝑁2 = 𝐶6−1+15 = 𝐶20 = 15504 15 15 𝑁3 = 𝐶6−1+15 = 𝐶20 = 15504 10 10 𝑁4 = 𝐶6−1+10 = 𝐶15 = 3003 Vì vậy số nghiệm thỏa mãn yêu cầu bài toán là: 𝑁 = 𝑁1 − 𝑁2 − 𝑁3 + 𝑁4 = 53130 − 15504 − 15504 + 3003 = 25125 25 http://www.ptit.edu.vn |
