Xem mẫu
- 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 66 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 nn ô vuông
Cho một lưới gồm nn ô 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.
nguon tai.lieu . vn
