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

Chia sẻ: Nguyễn Hà | Ngày: | Loại File: PDF | Số trang:62

Thêm vào BST

Báo xấu

407
lượt xem 34
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Download "Bài giảng Toán rời rạc - Chương 3: Lý thuyết tổ hợp" để tìm hiểu và nắm vững kiến thức toán cao cấp lý thuyết tổ hợp, các bài toán tồn tại, bài toán đếm...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

Chương 3: LÝ THUYẾT TỔ HỢP
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
BÀI TOÁN TỒN TẠ I
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 i  {0,1, ..., n  2}, i  1, n  n i  {1, 2, ..., n  1}, i  1, n  Theo nguyên lý Dirichlet thì có 2 người cùng số người quen.