Bài giảng Toán rời rạc - Chương 3: Lý thuyết tổ hợp

Chương 3: LÝLÝ THUYTHUYẾẾTT TTỔỔ HHỢỢPP 3. 1 BÀI TOÁN TỒN TẠI 3.2 BÀI TOÁN ĐẾM TỔ HỢP 3.3 BÀI TOÁN LIỆT KÊ 3.4 BÀI TOÁN TỐI ƯU BBÀÀII TOTOÁÁNN TTỒỒNN TTẠẠII MỞ ĐẦU Trong rất nhiều bài toán tổ hợp, việc chỉ ra sự tồn tại của một cấu hình tổ hợp thỏa mãn các tính chất cho trước có ý nghĩa quan trọng về mặt lí thuyết cũng như thực tế. Trong tổ hợp xuất hiện một bài toán quan trọng là Bài toán tồn tại: Xét sự tồn tại của các cấu hình tổ hợp thỏa mãn các tính chất cho trước. Một bài toán tồn tại tổ hợp xem là giải xong nếu hoặc chỉ ra một cách xây dựng cấu hình, hoặc chứng minh rằng chúng không có. Tuy nhiên cả hai khả năng trên đều không phải dễ. Để thấy rõ sự phức tạp của vấn đề, dưới đây ta sẽ xét một số bài toán tồn tại tổ hợp cổ điển nổi tiếng. MỘT SỐ VÍ DỤ Bài toán 36 sĩ quan: Bài toán này do nhà toán học Euler đưa ra, nội dung như sau: Người ta triệu tập từ 6 trung đoàn, mỗi trung đoàn 6 sĩ quan có 6 cấp bậc khác nhau: thiếu úy, trung úy, thượng úy, đại úy, thiếu tá, trung tá. Hỏi có thể sắp xếp 36 sĩ quan này thành hình vuông 66 sao cho mỗi hàng dọc cũng như hàng ngang đều có đại diện của 6 trung đoàn và cũng có 6 cấp bậc khác nhau. Để đơn giản ta dùng các chữ cái in hoa A, B, C, D, E, F để chỉ 6 trung đoàn và các chữ cái thường a, b, c, d, e, f để chỉ 6 cấp bậc. Bài toán có thể tổng quát hóa bằng cách thay số 6 bằng n. Trong trường hợp n = 4, một lời giải của bài toán 16 sĩ quan: Ab Dd Ba Cc Bc Ca Ad Db Cd Bb Dc Aa Da Ac Cb Bd Một lời giải cho trường hợp n = 5 của bài toán 25 sĩ quan: Aa Bb Cc Dd Ee Cd De Ea Ab Bc Eb Ac Bd Ce Da Be Ca Db Ec Ad Dc Ed Ae Ba Cb Do lời giải của bài toán có thể biểu diễn bởi hai hình vuông với các chữ cái hoa và thường xếp cạnh nhau nên bài toán tổng quát còn có tên gọi là bài toán hình vuông la tinh trực giao. Sinh thời, nhà toán học Euler đã mất nhiều công sức đi tìm lời giải cho bài toán nhưng đã không thành công. Vì vậy, ông đã đưa ra giả thuyết rằng lời giải cho bài toán tổng quát là không tồn tại. Giả thuyết này được nhà toán học Pháp Tarri chứng minh năm 1901 bằng cách duyệt tất cả các khả năng xếp. Dựa trên giả thuyết không tồn tại lời giải cho n = 2 và n = 6, Euler còn đưa ra giả thuyết tổng quát hơn là: Không tồn tại hình vuông la tinh trực giao cấp 4k + 2. Giả thuyết này tồn tại suốt 2 thế kỷ. Mãi đến năm 1960 ba nhà toán học Mỹ là Boce, Parker, Sricanda mới chỉ ra một lời giải với n = 10 và sau đó đưa ra phương pháp xây dựng hình vuông la tinh trực giao cấp 4k + 2 với k > 1. Bài toán 2n điểm trên lưới nn ô vuông Cho một lưới gồm nn ô vuông. Hỏi có thể đặt 2n điểm trên lưới sao cho không có 3 điểm nào cùng nằm trên 1 hàng hay 1 cột? Hiện nay người ta mới biết lời giải đối với n  15. Sau đây là lời giải với n = 12.                         NGUYÊN LÝ DIRICHLET Nguyên lý Dirichlet (nguyên lý chuồng chim): Nếu xếp nhiều hơn n đối tượng vào n chiếc hộp thì tồn tại hộp chứa ít nhất 2 đối tượng. Ví dụ: 1. Trong 367 người bao giờ cũng có ít nhất 2 người trùng ngày sinh nhật, bởi vì trong năm có nhiều nhất 366 ngày. 2. Trong một kì thi học sinh giỏi, điểm bài thi được dánh giá bời một số nguyên trong khoảng từ 0 đến 100. Hỏi rằng có ít nhất bao nhiêu thí sinh dự thi để chắc chắn tìm được hai học sinh có kết quả thi như nhau? Nguyên lý Dirichlet tổng quát Nếu xếp n đối tượng vào k chiếc hộp thì tồn tại hộp chứa không ít hơn n/k đối tượng. Ví dụ: 1. Trong 100 người thì có ít nhất 9 người trùng tháng sinh. 2. Có 5 loại học bổng khác nhau. Hỏi rằng phải có ít nhất bao nhiêu sinh viên để chắc chắn rằng có ít nhất 6 người cùng nhận học bổng như nhau? Ví dụ: Chứng minh rằng: Trong hội nghị có n người bao giờ cũng có 2 người có số người quen trong số những người tham dự bằng nhau. HD Gọi ni là số người quen của người thứ i (i = 1, 2,...,n), ni {0, 1, , n – 1}. Nhưng không thể đồng thời xảy ra có người không quen ai cả và có người quen (n – 1) người còn lại. Vậy xảy ra một trong hai trường hợp sau: n {0,1,...,n  2}, i 1,n  i ni {1,2,...,n 1}, i 1,n Theo nguyên lý Dirichlet thì có 2 người cùng số người quen. 3.2 BÀI TOÁN ĐẾM 3.2.1 CÁC NGUYÊN LÝ CƠ BẢN 3.2.2 CÁC CẤU HÌNH TỔ HỢP ĐƠN GiẢN 3.2.3 MỘT SỐ VÍ DỤ ỨNG DỤNG 3.2.4 NGUYÊN LÝ BÙ TRỪ 3.2.1 MỘT SỐ NGUYÊN LÍ CƠ BẢN a. Nguyên lí cộng: - Nếu A và B là hai tập rời nhau (AB = ) thì A B  A  B - Nếu A1, A2, Ak là k tập đôi một rời nhau thì A1  A2 ... Ak  A1  A2 ... Ak Chú ý: Nguyên lí cộng còn được phát biểu như sau: Một công việc được thực hiện theo k phương án: + Phương án 1: có m1 cách thực hiện + Phương án 2: có m2 cách thực hiện + Phương án k: có mk cách thực hiện Tổng số cách thực hiện công việc là: m1 + m2 + +mk b. Nguyên lí nhân: Một công việc được chia làm k bước thực hiện, bước thứ i có ni cách thực hiện. Khi đó tổng số cách thực hiện công việc: n1n2 nk (cách) Ví dụ 1: Một nhà hàng có thực đơn sau: Khai vị: 1. Salad 2. Súp Món ăn chính: 1. Thịt bò 2. Thịt lợn 3. Cá Đồ uống: 1. Trà 2. Sữa 3. Bia 4. Coca Có bao nhiêu cách chọn bữa ăn gồm: 1 món khai vị, 1 món chính và 1 loại đồ uống? Ví dụ 2: Cho 5 kí tự A, B, C, D, E (a) Có bao nhiêu xâu kí tự có độ dài 4 có thể lập được từ các kí tự đã cho nhưng không lặp kí tự. (b) Có bao nhiêu xâu kí tự trong (a) bắt đầu từ B. (c) Có bao nhiêu xâu kí tự trong (a) không bắt đầu từ B. HD: Gọi xâu s = abcd a) a có 5 cách chọn, b có 4 cách, c có 3 cách, d có 2 cách Theo nguyên lý nhân số xâu chữ là: 5.4.3.2 = 120 b) Số xâu chữ bắt đầu từ B: 4.3.2 = 24 c) Số xâu chữ không bắt đầu từ B: 120 – 24 = 196 Ví dụ 3: a- Đếm các xâu nhị phân có kích thước 1 byte. b-Đếm các xâu nhị phân có kích thước 1 byte có hai bit đầu 10 hoặc 01 HD: a- 1byte = 8 bit, mỗi bit có 2 cách chọn (0 hoặc 1). Theo nguyên lí nhân có: 28 = 256 số 1 byte b- Bắt đầu bằng 10 có 26 = 64 số - Bắt đầu bằng 01 có 26 = 64 số Vậy có 64 + 64 =128 số 1 byte bắt đầu bằng 10 hoặc 01 3.2.2 CÁC CẤU HÌNH TỔ HỢP ĐƠN GIẢN a. Hoán vị * Một hoán vị của n phần tử là một cách sắp xếp thứ tự n phần tử đó. * Số các hoán vị của n phần tử: n! Ví dụ 4: Có bao nhiêu cách xếp 3 người Việt, 5 người Pháp và 6 người Mỹ ngồi một ghế dài sao cho người cùng quốc tịch ngồi cạnh nhau? b. Chỉnh hợp lặp * Một chỉnh hợp lặp chập k của n phần tử là một bộ có thứ tự gồm k phần tử lấy từ n phần tử đã cho, các phần tử có thể được lặp lại. * Số các chỉnh hợp lặp chập k của n phần tử: k k An  n Ví dụ 5: Có bao nhiêu số hàng trăm được thiết lập từ các chữ số: 1, 2, 3, 4, 5? c. Chỉnh hợp (không lặp) * Một chỉnh hợp chập k của n phần tử là một bộ có thứ tự gồm k phần tử lấy từ n phần tử đã cho, các phần tử không được lặp lại. * Số các chỉnh hợp không lặp chập k của n phần tử: n! Ak  n.(n 1)...(n  k 1)  n (n  k)! Ví dụ 6: Có bao nhiêu số hàng trăm với 3 chữ số khác nhau được thiết lập từ các chữ số: 1, 2, 3, 4, 5? d. Tổ hợp * Một tổ hợp chập k của tập X gồm n phần tử là một tập con có k phần tử của X. * Số các tổ hợp chập k của n phần tử: n! C k  n k!(n  k)! Ví dụ 7: a. Có n đội thi đấu vòng tròn. Hỏi phải tổ chức chức bao nhiêu trận đấu? b. Có bao nhiêu xâu nhị phân độ dài 32 mà trong đó có đúng 6 số 1? HD: 2 a. Số trận đấu: Cn b. Số xâu nhị phân: 6 C32 3.2.3 MỘT SỐ VÍ DỤ ỨNG DỤNG a. Bài toán đếm cách xếp chỗ Ví dụ 8: a. Có bao nhiêu hoán vị của các chữ cái trong xâu ABCDEF mà trong đó có chứa xâu con DEF? b. Có bao nhiêu hoán vị của các chữ cái trong xâu ABCDEF mà trong đó 3 chữ các D, E, F đứng cạnh nhau? Ví dụ 9: Một nhóm sinh viên có 7 nam và 5 nữ xếp thành hàng dọc. Hỏi có bao nhiêu cách sắp xếp hàng để không có 2 nữ nào đứng cạnh nhau? (*Cho sv đề xuất cách giải, nếu ko được gọi 2 sinh lên ghi 2 cách xếp sau cho 2 nữ không đứng cạnh nhau*=> tổng quát cách giải.*) Ví dụ 10: Có bao nhiêu cách xếp k bít 0 và m bít 1 (k  m) trên hàng ngang sao cho không có 2 bit 0 kề nhau? b. Bài toán đếm số đường đi Ví dụ 11: Cho lưới hình chữ nhật gồm mxn ô vuông (xem hình vẽ) (0, m) (n, m) (0, 0) (n, 0) Có bao nhiêu cách đi từ nút (0, 0) đến (n, m) nếu chỉ cho phép đi trên cạnh các ô vuông theo chiều sang phải hoặc lên trên? 3.2.4 NGUYÊN LÝ BÙ TRỪ - Cho A và B là hai tập bất kì thì A B  A  B  A B - A, B, C là 3 tập bất kì thì A B C  A  B  C  A B  AC  B C  A B C Ví dụ 12: Có bao nhiêu xâu nhị phân có độ dài 10 hoặc bắt đầu bởi 00 hoặc kết thúc bởi 11? 3.3 BÀI TOÁN LIỆT KÊ 3.3.1 GiỚI THIỆU BÀI TOÁN 3.3.2 PHƯƠNG PHÁP SINH 3.3.3 THUẬT TOÁN QUAY LUI 3.3.1 GiỚI THIỆU BÀI TOÁN Ví dụ: Một băng video có thể ghi được C giây. Ta có n phim video với lượng thời gian tương ứng là: t1, t2, , tn. Ta phải chọn k phim i1, i2, , ik sao cho tổng thời gian:  ti i{i1 ,i2 ,...ik } lớn nhất và không vượt quá C. Một cách chân phương là liệt kê tất cả các tập con {i1, i2, , ik} của tập gồm n phim và chọn tập có tổng trên là lớn nhất và không vượt quá C. Trong nhiều trường hợp, khi không có thuật toán để giải quyết những bài toán như trên thì phương pháp liệt kê với sự trợ giúp của máy tính vẫn là phương pháp khả dĩ. * Bài toán liệt kê là bài toán đưa ra danh sách tất cả cấu hình tổ hợp có thể có. * Bài toán liệt kê xác định thuật toán xây dựng lần lượt cấu hình quan tâm, thuật toán cần bảo đảm các yêu cầu sau: - Không lặp lại cấu hình - Không bỏ sót cấu hình 3.3.2 PHƯƠNG PHÁP SINH a. Thứ tự từ điển Cho s = s1, s2,..., sp và t = t1, t2,..., tq là hai dãy gồm các số hoặc ký tự. Ta nói rằng s nhỏ hơn t (theo nghĩa từ điển), ký hiệu s < t, nếu thoả mãn 1 trong 2 điều kiện sau đây: i. p < q và si = ti với mọi i = 1, 2, ..., p ii. Tồn tại k  min{p, q} sao cho: si = ti với mọi i = 1, 2,...,k – 1 và sk < tk Ví dụ: * 132 1324 * AN ANH * BANDIT BANK * 13246 1341 b. Thuật toán sinh tổng quát Kí hiệu s là cấu hình hiện hành, so là cấu hình đầu tiên (theo thứ tự từ điển) + B1: Khởi tạo, gán s  so + B2: Kết xuất s + B3: Kiểm tra tiêu chuẩn kết thúc: Nếu s là cấu hình cuối thì kết thúc, ngược lại sang bước 4 + B4: Tìm cấu hình t đứng sau s theo thứ tự từ điển. Gán s  t và quay lại bước 2 c. Liệt kê tất cả các dãy nhị phân có độ dài bằng n * Phát biểu bài toán Cho n  N. Hãy liệt kê (theo nghĩa từ điển) tất cả các dãy nhị phân độ dài n, tức là dãy [b1, b2, ...,bn] với bi  {0, 1},  i = 1, 2, , n. Số dãy nhị phân là 2n và dãy nhị phân đầu tiên: so = [0, 0, ..., 0] Phương pháp tìm dãy kế tiếp Cho dãy nhị phân s = [s1, s2, , sn], ta tìm dãy kế tiếp t = [t1, t2, , tn]. - Từ dãy s, xuất phát từ sn đi từ phải sang trái tìm phần tử đầu tiên sm, 1  m  n, thỏa sm = 0. + Nếu không tìm thấy thì s = [1, 1, ..., 1] là dãy cuối cùng  kết thúc + Nếu tìm thấy thì ta xây dựng dãy t = [t1, t2, ..., tn] như sau: ti = si với i = 1, 2, ..., m – 1 tm = 1 ti = 0 với i = m + 1, m + 2, ...., n Ví dụ: Cho dãy nhị phân s = [010011], tìm dãy kế tiếp? Thuật toán liệt kê dãy nhị phân - Đầu vào: nhập n - Đầu ra: Danh sách tất cả các dãy nhị phân độ dài n theo thứ tự từ điển tăng dần. + B1: Khởi tạo: Gán si = 0 với mọi i = 1, 2, ...., n + B2: Kết xuất s. + Bước 3: Tìm m thoả mãn m = max{i | si = 0}  Nếu không tìm thấy thì s = [1,1,...,1] là dãy cuối cùng  kết thúc  Nếu tìm thấy ta đặt: sm  1 và si  0 với mọi i = m + 1, m + 2, ..., n Quay lại bước 2. VÍ DỤ Liệt kê các dãy nhị phân có độ dài 3 3.3.3 THUẬT TOÁN QUAY LUI Nội dung chính của thuật toán này là xây dựng dần các thành phần của cấu hình bằng cách thử tất cả các khả năng. Giả thiết cấu hình cần được mô bằng một dãy gồm n thành phần x1x2...xn Giả sử đã xác định được i – 1 thành phần x1, x2, ..., xi-1. Ta xác định thành phần thứ i là xi bằng cách duyệt tất cả các khả năng có thể có (đánh số các khả năng từ 1 đến ni). Với mỗi khả năng j, kiểm tra xem khả năng j có chấp nhận được không. Có thể có 2 trường hợp sau: - Nếu j được chấp nhận thì xác định được xi theo j, sau đó nếu i = n thì ta có được một cấu hình, còn nếu i < n thì tiến hành xác định xi+1 - Nếu thử tất cả các khả năng mà không có khả năng nào được chấp nhận thì quay lại bước trước để xác định lại xi-1 Bước xác định xi có thể được diễn tả qua thủ tục đệ quy sau: Procedure try(i:integer) var j: integer begin for j  1 to ni do if then begin if i = n then else try(i + 1); end; End; Đoạn chương trình chính của bài toán liệt kê có dạng: Begin Init; Try(1) End. VÍ DỤ Đoạn chương trình liệt kê các dãy nhị phân có độ dài n: Var n:integer x: array[0..20] of 0..1 Procedure Try(i:integer); Var j: integer; Begin for j 0 to 1 do begin x[i] j; if i = n then Result else Try(i+1) end; Begin Init; Try(1); End.