Tài liệu Toán 11 Tài liệu bồi dưỡng học sinh giỏi Chuyên đề 20 TỔ HỢP VÀ RỜI RẠC Lê Hoành Phò File word là tài liệu môn Toán trong chương trình Lớp 11 được cungthi.vn tổng hợp và biên soạn. Tạo nguồn tài liệu giúp các bạn trong việc ôn tập
Những địa chỉ uy tín để bạn mua sách
Nội dung tóm tắt
Đặt mua trọn bộ chuyên đề lớp 11 môn Toán file word
Cách 1: Soạn tin “ Đăng ký bộ đề chuyên đề lớp 11 Toán” gửi đến số 0982.563.365
Cách 2: Đăng ký tại link sau http://dethithpt.com/dangkytoan/
Chuyên đề 20: TỔ HỢP VÀ RỜI RẠC
1. KIẾN THỨC TRỌNG TÂM
Tổ hợp và xác suất CX
Số hoán vị của tập A có n phần tử:
Số chỉnh hợp n chập k:
Số tổ hợp n chập k:
Xác suất:
Xác suất có điều kiện:
Nhị thức Newton:
Cho n tập là n tập hợp hữu hạn thì số phần tử:
Cho ánh xạ f từ tập hữu hạn X có n phần tử vào tập hữu hạn Y có m phần tử.
Số ánh xạ f từ X và Y là.
Số đơn ánh f từ X vào Y làvới
Số toàn ánh f từ X vào Y là khi
Số song ánh f từ X và Y là khi
Nguyên tắc Dirichlê
Nếu nhốt con thỏ vào k chuồng (k nguyên dương) thì tồn tại một chuồng chứa ít nhất 2 con. Nếu nhốt con thỏ vào k chuồng (k nguyên dương) thì tồn tại một chuồng chứa ít nhất 3 con.
Nếu nhốtcon thỏ vào k chuồng (k, n nguyên dương) thì tồn tại một chuồng chứa ít nhất con. Nguyên tắc cực hạn
Tồn tại độ đo lớn nhất và độ đo nhỏ nhất hay đại lượng lớn nhất và đại lượng nhỏ nhất của tập hữu hạn khác rỗng các độ đo hay các đại lượng.
Bất biến và đơn biến
Đại lượng bất biến, tính chất bất biến là những đại lượng hay tính chất không thay đổi trong quá trình thực hiện các phép biến đổi nào đó.
Đại lượng đơn biến, tính chất đơn biến là những đại lượng hay tính chất thay đổi một chiều, hoặc tăng thêm hoặc giảm đi trong quá trình thực hiện các phép biến đổi nào đó.
Đồ thị
Bổ đề bắt tay: Cho đồ thị thì tổng bậc các đỉnh củạ đồ thị là số chẵn và
Định lý Tocran: Nếu đồ thị G có n đỉnh và số tam giác của G là thì
số cạnh:
2. CÁC BÀI TOÁN
Bài toán 20 .1 : Tính:
Hướng dẫn giải
Xét hàm số thì:
Do đó:
Bài toán 20. 2: Tìm tất cả các cặp số tự nhiên dương n và k thoả:
Hướng dẫn giải
Ta có:
Vì nên (1)
Mà nên (1) xả ra
Do đó
Thử lại Tóm lại
Bài toán 20. 3: Chứng minh rằng:
Hướng dẫn giải
Với ta đặt trong đó tổng được lấy từ
cho đến hết những số hạng khác 0.
Ta có:
Ta có , suy ra (1)
Ta có , từ đó
Từ (1) ta có nếu .Do
nên ta được:
Suy ra điều phải chứng minh.
Bài toán 20. 4: Cho các số nguyên dương m và n sao cho.
Chứng minh rằng:
Hướng dẫn giải
Ta có:
Ngoài ra và
Do đó, các bất đẳng thức cần chứng minh tương đương với
Ta có:
vì i là số nguyên nằm giữa 1 và n. Suy ra:
do đó ta được:
Vậy các bất đẳng thức đã cho là đúng.
Bài toán 20. 5: Cho n nguyên dươngvà
Chứng minh:
Hướng dẫn giải
Ta có: và khai triển nhị thức
Bài toán 20. 6: Hỏi từ các chữ số 1, 2, 3, 4, 5 ta có thể lập được tất cả bao nhiêu số có 15 chữ số mà trong mỗi số mỗi chữ số đều có mặt đúng 3 lần và không có chữ số nào chiếm 3 vị trí liên tiếp trong số?
Hướng dẫn giải
Gọi X là tập gồm tất cả các số thoả mãn yêu cầu đề bài.
A là tập gồm tất cả các số có 15 chữ số được lập nên bởi các chữ số 1, 2, 3, 4, 5 mà mỗi chữ số đều có mặt đúng 3 lần trong số.
Khi đó: Với là tập gồm tất cả các số thuộc A mà chữ số i
chiếm đúng 3 vị trí liên tiếp
Xét ta chứng minh được và
Áp dụng công thức:
Bài toán 20. 7: Cho các số nguyên dương k và n với. Hỏi tất cả có bao nhiêu chỉnh hợp chập của n số nguyên dương đầu tiên, mà mỗi chỉnh hợp thoả mãn ít nhất một trong hai điều kiện sau:
1) Tồn tại sao cho s < t và >
2) Tồn tại sao cho không chia hết cho 2.
Hướng dẫn giải
Gọi A là tập hợp tất cả chỉnh hợp chập k của n số nguyên dương đầu tiên và A1 là tập hợp tất cả chỉnh hợp thoả mãn yêu cầu của bài ra.
Nếu kí hiệu chỉnh hợp và
thì rõ ràngvà . Suy ra:
Bây giờ ta xét . Với mỗi ta đều có với mọi
và với mọi
Ta chứng minh: từ đó ta có:
Bài toán 20. 8: Trong mặt phẳng cho 100 điểm phân biệt sao cho không có 3 điểm nào thẳng hàng.Chứng minh rằng trong số các tam giác được tạo thành từ 100 điểm đó, có không quá 70% các tam giác nhọn.
Hướng dẫn giải
Từ 4 điểm phân biệt không có 3 điểm nào thẳng hàng, nhiều lắm là có 3 tam giác nhọn. Từ kết quả này, suy ra với 5 điểm phân biệt không có 3 điểm nào thẳng hàng, ta nhận được 10 tam giác và có không quá 7 tam giác nhọn.
Với 10 điểm phân biệt không có 3 điểm nào thẳng hàng, số cực đại các tam giác nhọn tạo thành là: số các tập con 4 điểm nhân cho 3 rồi chia cho số các tập con 4 điểm chứa 3 điểm cho trước. Trong khi đó, số tất cả các tam giác tạo thành cũng có biểu thức tương tự như í trên nhưng thay vì nhân 3 ta nhân cho 4. Do vậy số các tam giác nhọn chiếm không quá 3/4 số tất cả các tam giác (đối với 10 điểm).
Lí luận tương tự, ta xét 100 điểm phân biệt sao cho không có 3 điểm nào thẳng hàng, số cực đại các tam giác nhọn tạo thành là: số các tập con 5 điểm nhân cho 7 rồi chia cho số các tập con 5 điểm chứa 3 điểm cho trước.
Trong khi đó, số tất cả các tam giác tạo thành cũng có biểu thức tương tự như trên nhưng thay vì nhân 7 ta nhân cho 10. Do vậy số các tam giác nhọn chiế
