Chương 1: Những kiến thức cơ bản a) X ∨ (Y1 ∧ Y2 ∧. ∨ ( X ∧ Yn ) c) ( X 1 ∨ X 2 ∨ ∨ Xn ⇔ X1 ∧ X1 ∧ ∧ Xn d) X1 ∧ X 2 ∧ ∧ Xn ⇔ X1 ∨ X 2 ∨ ∨ Xn Bài 7. Cho A, B, C là các tập hợp. Chứng minh rằng: ( A − B) − C = ( A − C ) − ( B − C ) Bài 8.
Cho A, B, C là các tập hợp. Chứng minh rằng: ( B − A) ∪ (C − A) = ( B ∪ C ) − A Bài 9. Chứng minh rằng nếu A, B là các tập hợp thì: ( A ∩ B) ∪ ( A ∩ B ) = A Bài 10. Cho A, B, C là các tập hợp.
Chứng minh rằng: a) A ∩ B ∩ C = A ∪ B ∪ C b) ( A ∩ B ∩ C ) ⊆ ( A ∩ B ) c) ( A − B) − C ⊆ ( A − C ) d ) ( A − C ) ∩ (C − B ) = Φ e) ( B − A) ∪ (C − A) = ( B ∪ C ) − A f) A− B = A∩ B g ) ( A ∩ B) ∪ ( A ∩ B = A 21 Chương 2: Bài toán đếm và bài toán tồn tại CHƯƠNG II: BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI Đếm các đối tượng có những tính chất nào đó là một bài toán quan trọng của lý thuyết tổ hợp. Giải quyết tốt bài toán đếm giúp ta giải nhiều bài toán khác nhau trong đánh giá độ phức tạp tính toán của các thuật toán và tìm xác suất rời rạc các biến cố. Phương pháp chung để giải bài toán đếm được dựa trên các nguyên lý đếm cơ bản (nguyên lý cộng, nguyên lý nhân). Một số bài toán đếm phức tạp hơn được giải bằng cách qui về các bài toán con để sử dụng được các nguyên lý đếm cơ bản hoặc tìm ra hệ thức truy hồi tổng quát.
Nội dung chính được đề cập trong chương này bao gồm: 9 Các nguyên lý đếm cơ bản 9 Nguyên lý bù trừ 9 Hoán vị và tổ hợp 9 Hệ thức truy hồi 9 Qui về các bài toán con 9 Giới thiệu bài toán tồn tại 9 Phương pháp phản chứng giải quyết bài toán tồn tại. 9 Nguyên lý Dirichlet giải quyết bài toán tồn tại. Bạn đọc có thể tìm hiểu nhiều kỹ thuật đếm cao cấp hơn trong tài liệu [1], [2] trong phần tham khảo của tài liệu này. NHỮNG NGUYÊN LÝ ĐẾM CƠ BẢN 2.
Nguyên lý c ng Giả sử có hai công việc. Việc thứ nhất có thể tiến hành bằng n1 cách, việc thứ hai có thể tiến hành bằng n2 cách và nếu hai việc này không thể tiến hành đồng thời. Khi đó sẽ có n1 + n2 cách để giải giải quyết một trong hai việc trên. Chúng ta có thể mở rộng qui tắc cộng cho trường hợp nhiều hơn hai công việc.
Giả sử các việc T1, T2,., Tm có thể làm tương ứng bằng n1, n2,., nm cách và giả sử không có hai việc Ti, Tj nào làm việc đồng thời (i,j = 1, 2,. +nm cách thực hiện một trong các công việc T1, T2,. Qui tắc cộng được phát biểu dưới dạng của ngôn ngữ tập hợp như sau: Nếu A và B là hai tập rời nhau (A ∩ B = φ) thì: N(A∪B) = N(A) + N(B). 22 Chương 2: Bài toán đếm và bài toán tồn tại Nếu A1, A2,., An là những tập hợp rời nhau thì: N(A1 ∪ A2 ∪.
Giả sử cần chọn hoặc một cán bộ hoặc một sinh viên tham gia một hội đồng của một trường đại học. Hỏi có bao nhiêu cách chọn vị đại biểu này nếu như có 37 cán bộ và 63 sinh viên. Giải: Gọi việc thứ nhất là chọn một cán bộ từ tập cán bộ ta có 37 cách. Gọi việc thứ hai là chọn một sinh viên từ tập sinh viên ta có 63 cách.
Vì tập cán bộ và tập sinh viên là rời nhau, theo nguyên lý cộng ta có tổng số cách chọn vị đại biểu này là 37 + 63 = 100 cách chọn. Một đoàn vận động viên gồm môn bắn súng và bơi được cử đi thi đấu ở nước ngoài. Số vận động viên nam là 10 người. Số vận động viên thi bắn súng kể cả nam và nữ là 14 người.
Số nữ vận động viên thi bơi bằng số vận động viên nam thi bắn súng. Hỏi đoàn có bao nhiêu người. Giải: Chia đoàn thành hai tập, tập các vận động viên nam và tập các vận động viên nữ. Ta nhận thấy tập nữ lại được chia thành hai: thi bắn súng và thi bơi.
Thay số nữ thi bơi bằng số nam thi bắn súng, ta được số nữ bằng tổng số vận động viên thi bắn súng. Từ đó theo nguyên lý cộng toàn đoàn có 14 + 10 = 24 người. giá trị của biến k sẽ bằng bao nhiêu sau khi thực hiện đoạn chương trình sau: k:= 0 for i1:= 1 to n1 k:= k+ 1 for i2:= 1 to n2 k:= k+ 1. for im:= 1 to nm k:= k+ 1 Giải: Coi mỗi vòng for là một công việc, do đó ta có m công việc T1, T2,.
Trong đó Ti thực hiện bởi ni cách (i= 1, 2,. Vì các vòng for không lồng nhau hay các công việc không thực hiện đồng thời nên theo nguyên lý cộng tổng tất cả các cách để hoàn thành T1, T2,. Nguyên lý nhân Giả sử một nhiệm vụ nào đó được tách ra hai công việc. Việc thứ nhất được thực hiện bằng n1 cách, việc thứ hai được thực hiện bằng n2 cách sau khi việc thứ nhất đã được làm, khi đó sẽ có n1.n2 cách thực hiện nhiệm vụ này.
Nguyên lý nhân có thể được phát biểu tổng quát bằng ngôn ngữ tập hợp như sau: 23 Chương 2: Bài toán đếm và bài toán tồn tại Nếu A1, A2,., Am là những tập hợp hữu hạn, khi đó số phần tử của tích đề các các tập này bằng tích số các phần tử của mỗi tập thành phần. Hay đẳng thức: N (A1× A2×. Am thì N(Ak) = N(A)k Ví dụ 1. Giá trị của k sẽ bằng bao nhiêu sau khi ta thực hiện đoạn chương trình sau: k:= 0 for i1 = 1 to n1 for i2 = 1 to n2 ……… for in = 1 to nm k:= k + 1 Giải: Giá trị khởi tạo k=0.
Mỗi vòng lặp kồng nhau đi qua giá trị của k được tăng lên 1 đơn vị. Gọi Ti là việc thi hành vòng lặp thứ i. Khi đó, số lần vòng lặp là số cách thực hiện công việc. Số cách thực hiện công việc Tj là nj (j=1,2,.
Theo qui tắc nhân ta vòng lặp kép được duyệt qua n1 +n2 +.+nm lần và chính là giá trị của k. Người ta có thể ghi nhãn cho những chiếc ghế của một giảng đường bằng một chữ cái và sau đó là một số nguyên nhỏ hơn 100. Bằng cách như vậy hỏi có nhiều nhất bao nhiêu chiếc ghế có thể ghi nhãn khác nhau. Giải: Có nhiều nhất là 26 x 100 = 2600 ghế được ghi nhãn.
Vì kí tự gán nhãn đầu tiên là một chữ cái vậy có 26 cách chọn các chữ cái khác nhau để ghi kí tự đầu tiên, tiếp theo sau là một số nguyên dương nhỏ hơn 100 do vậy có 100 cách chọn các số nguyên để gán tiếp sau của một nhãn. Theo qui tắc nhân ta nhận được 26 x 100 = 2600 nhãn khác nhau. Có bao nhiêu xâu nhị phân có độ dài 7. Giải: một xâu nhị phân có độ dài 7 gồm 7 bít, mỗi bít có hai cách chọn (hoặc giá trị 0 hoặc giá trị 1), theo qui tắc nhân ta có 2.2 = 27 = 128 xâu bít nhị phân độ dài 7.
Có bao nhiêu hàm đơn ánh xác định từ một tập A có m phần tử nhận giá trị trên tập B có n phần tử. Giải: Trước tiên ta nhận thấy, nếu m >n thì tồn tại ít nhất hai phần tử khác nhau của A cùng nhận một giá trị trên B, như vậy với m>n thì số các hàm đơn ánh từ A→B là 0. Nếu m<=n, khi đó phần tử đầu tiên của A có n cách chọn, phần tử thứ hai có n-1 cách chọn,., phần tử thứ k có n-k+1 cách chọn. Theo qui tắc nhân ta có n(n-1) (n-2).(n-m+1) hàm đơn ánh từ tập A sang tập B.
Dạng của số điện thoại ở Bắc Mỹ được qui định như sau: số điện thoại gồm 10 chữ số được tách ra thành một nhóm mã vùng gồm 3 chữ số, nhóm mã chi nhánh gồm 3 chữ số và nhóm mã máy gồm 4 chữ số. Vì những nguyên nhân kỹ thuật nên có một số hạn chế đối với một 24 Chương 2: Bài toán đếm và bài toán tồn tại số con số. Ta giả sử, X biểu thị một số có thể nhận các giá trị từ 0.9, N là số có thể nhận các chữ số từ 2.9, Y là các số có thể nhận các chữ số 0 hoặc 1. Hỏi theo hai dự án đánh số NYX NNX XXXX và NXX NXX XXXX có bao nhiêu số điện thoại được đánh số khác nhau ở Bắc Mỹ.
Giải: đánh số theo dự án NYX NNX XXXX được nhiều nhất là: 8 x 2 x 10 x 8 x 8 x10 x10 x10 x 10 x 10 x10 = 2 x 83 x 106 = 1 024. 106 đánh số theo dự án NXX NXX XXXX được nhiều nhất là: 8 x 10 x 10 x 8 x 10 x10 x10 x10 x 10 x 10 x10 = 82 x 108 = 64. Dùng qui tắc nhân hãy chỉ ra rằng số tập con của một tập S hữu hạn là 2N(S). Giải: Ta liệt kê các phần tử của tập S là s1, s2,.
Xây dựng một xâu bít nhị phân dài N(S) bít, trong đó nếu bít thứ i có giá trị 0 thì phần tử si ∉S, nếu bít thứ i có giá trị 1 thì phần tử si∈S (i=1, 2,. Như vậy, theo nguyên lý nhân, số tập con của tập hợp S chính là số xâu bít nhị phân có độ dài N(S). Theo ví dụ 3, chúng ta có 2N(S) xâu bít nhị phân độ dài N(S). NGUYÊN LÝ BÙ TR Trong một số bài toán đếm phức tạp hơn.
Nếu không có giả thiết gì về sự rời nhau giữa hai tập A và B thì N(A∪B) = N(A) + N(B) – N(A∩B). lớp toán học rời rạc có 25 sinh viên giỏi tin học, 13 sinh viên giỏi toán và 8 sinh viên giỏi cả toán và tin học. Hỏi lớp có bao nhiêu sinh viên nếu mỗi sinh viên hoặc giỏi toán hoặc học giỏi tin học hoặc giỏi cả hai môn? Giải: Gọi A tập là tập các sinh viên giỏi Tin học, B là tập các sinh viên giỏi toán.