ĐẠi học quốc gia hà NỘI
CHƯƠNG 3 - MỘT SỐ BÀI TOÁN TỔ HỢP SỬ DỤNG PHÉP ĐẾM NÂNG CAO
tải về 0.86 Mb.
|
- Điều hướng trang này:
- 3.1 Một số bài toán sử dụng nguyên lư bù trừ.
- 3.1.2 Các bài toán giải bằng phương pháp bù trừ.
CHƯƠNG 3 - MỘT SỐ BÀI TOÁN TỔ HỢP SỬ DỤNG PHÉP ĐẾM NÂNG CAOChương này tŕnh bày một số bài toán sử dụng các phương pháp đếm nâng cao thường gặp trong các đề thi học sinh giỏi, đề thi quốc gia, thi quốc tế.
Khi hai công việc có thể được làm đồng thời, ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc. Ta có thể phát biểu nguyên lư đếm này bằng ngôn ngữ tập hợp. Cho A1, A2 là hai tập hữu hạn, khi đó |A1 A2| = |A1| + |A2| |A1 A2|. Từ đó với ba tập hợp hữu hạn A1, A2, A3, ta có:
| A1 A2 ... Ak| = N1 N2 + N3 ... + (1)k-1Nk, trong đó Nm (1 m k) là tổng phần tử của tất cả các giao m tập lấy từ k tập đă cho, nghĩa là
Bây giờ ta đồng nhất tập Am (1 m k) với tính chất Am cho trên tập vũ trụ hữu hạn U nào đó và đếm xem có bao nhiêu phần tử của U sao cho không thỏa măn bất kỳ một tính chất Am nào. Gọi là số cần đếm, N là số phần tử của U. Ta có: = N | A1 A2 ... Ak| = N N1 + N2 ... + (1)kNk, trong đó Nm là tổng các phần tử của U thỏa măn m tính chất lấy từ k tính chất đă cho. Công thức này được gọi là nguyên lư bù trừ. Nó cho phép tính qua các Nm trong trường hợp các số này dễ tính toán hơn.
Bài 72: Một chuyến bay có 67 hành khách. Trong đó có 47 người sử dụng tốt Anh, 35 người sử dụng tốt tiếng Đức, 20 người sử dụng tốt tiếng Pháp. Hơn nữa có 23 người sử dụng tốt hai thứ tiếng Anh và Đức, 12 người sử dụng tốt hai tiếng Anh và Pháp, 11 người sử dụng tốt hai tiếng Đức và Pháp. Và có 5 người sử dụng tốt cả ba thứ tiếng. T́m số hành khách không sử dụng được bất ḱ ngoại ngữ nào? Giải
Gọi A, B, C lần lượt là các hành khách sử dụng tốt ngoại ngữ là tiếng Anh, tiếng Đức, tiếng Pháp. Số các hành khách biết ít nhất một ngoại ngữ là: Vậy số hành khách không sử dụng được bất ḱ ngoại ngữ nào là 67 – 61 =6 Bài 73: Giáo viên chủ nhiệm của một lớp tiểu học yêu cầu lớp trưởng báo cáo thống kê theo mẫu và đọc trước lớp. Bản báo cáo như sau: Lớp có 45 học sinh, 30 học sinh nam. Lớp có 30 học sinh đạt điểm tốt, trong đó có 16 học sinh nam. Có 28 học sinh chơi thể thao, trong số này có 18 học sinh nam và 17 học sinh đạt điểm tốt. Có 15 em đạt điểm tốt và tham gia chơi thể thao. Hăy chỉ ra rằng lớp trưởng đă thống kê sai. Giải:
Đặt R là tập hợp học sinh cả lớp. A là tập hợp học sinh nam. B là tập hợp học sinh có điểm tốt. C là tập hợp học sinh chơi thể thao. Khi đó số học sinh nữ, không chơi thể thao, có kết quả không tốt bằng Kết quả trên là vô lí. Vậy lớp trưởng đó báo cáo sai.
Giải:
Có 8! Cách sắp xếp 8 con xe lên bàn cờ quốc tế sao cho không có con nào ăn con nào. Ta cần đếm số cách xếp không hợp lệ, tức là số cách xếp có ít nhất một con xe nằm trên đường chéo. Gọi Ai là tập hợp các cách xếp có quân xe nằm ở ô (i,j). ta cần t́m . Nhưng dễ dàng thấy rằng nên theo nguyên lư bù trừ ta có . Như vậy số cách sắp xếp 8 con xe lên bàn cờ quốc tế đă bị gạch đi một đường chéo chính sao cho không có con nào ăn con nào bằng : Bài 75: Có n lá thư và n phong b́ ghi sẵn địa chỉ. Bỏ ngẫu nhiên các lá thư vào các phong b́. Hỏi xác suất để xảy ra không một lá thư nào đúng địa chỉ. Giải
Mỗi phong b́ có n cách bỏ thư vào, nên có tất cả n! cách bỏ thư. Vấn đề c̣n lại là đếm số cách bỏ thư sao cho không lá thư nào đúng địa chỉ. Gọi U là tập hợp các cách bỏ thư và Am là tính chất lá thư thứ m bỏ đúng địa chỉ. Khi đó theo công thức về nguyên lư bù trừ ta có: = n! N1 + N2 ... + (1)nNn, trong đó Nm (1 m n) là số tất cả các cách bỏ thư sao cho có m lá thư đúng địa chỉ. Nhận xét rằng, Nm là tổng theo mọi cách lấy m lá thư từ n lá, với mỗi cách lấy m lá thư, có (n-m)! cách bỏ để m lá thư này đúng địa chỉ, ta nhận được: Nm = (n - m)! = và = n!(1 + ... + (1)n ), trong đó = là tổ hợp chập m của tập n phần tử (số cách chọn m đối tượng trong n đối tượng được cho). Từ đó xác suất cần t́m là: 1 + ... + (1)n . Một điều lư thú là xác suất này dần đến e-1 (nghĩa là c̣n > ) khi n khá lớn. Số trong bài toán này được gọi là số mất thứ tự và được kư hiệu là Dn. Dưới đây là một vài giá trị của Dn, cho ta thấy Dn tăng nhanh như thế nào so với n: n234567891011Dn12944265185414833133496133496114684570Bài 76:
Giải:
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ố 2, 3, 5, 7. Kí hiệu . Khi đó là tập hợp các số chia hết cho ít nhất một trong các số 2, 3, 5, 7 Ta có Do đó theo nguyên lư bù trừ ta có Vậy trong tập S có 280 – 216 = 64 số không chia hết cho 2, 3, 5, 7. Bài 77: Có bao nhiêu số tự nhiên khác nhau không vượt quá 1000 mà là bội của 10, 15, 35 hoặc 55. Giải
Đặt Khi đó ta có Mặt khác V́ vậy Lại có V́ vậy Và ta có V́ vậy Cuối cùng ta áp dụng nguyên lí bù trừ 3.3.1.3 Các bài toán tương tự Bài 78: T́m số các số nguyên từ 1 đến 10000 mà không chia hết cho 4, 6, 7, và 10. Bài 79: T́m số lượng các số nguyên dương từ 1 đến 10000 mà không phải là một b́nh phương hoặc lập phương của số nguyên. Bài 80: Một số được gọi là “không chính phương” nếu nó không chia hết cho b́nh phương của một số nguyên dương bất ḱ lớn hơn 1. T́m số lượng các số nguyên “không chính phương” nhỏ hơn 200. Bài 81: Có bao nhiêu chuỗi số có 6 chữ số mà không chứa “123” hoặc “456”. Bài 82: Xác định tất cả các nghiệm nguyên không âm của phương tŕnh Trong đó không vượt quá 8 Bài 83: Có bao nhiêu số nguyên dương nhỏ thua 420 và nguyên tố cùng nhau với 420.
|