Bài tập Toán rời rạc - Phần: Cặp ghép
2
4
3
4
1
2
5
3
1
3
2
5
1
5
4
Toán rời rạc phần Cặp ghép
Bài tập 7
1. Để hiện đại hóa phương pháp giảng dạy, số giờ lên
lớp của môn Toán rời rạc bị giảm đi, thay vào đó
mỗi sinh viên phải tham gia vào một số nhóm tự
học. Mỗi nhóm tự học này sẽ phải đề cử một sinh
viên đại diện cho nhóm để trình bày một nội dung
nghiên cứu trước lớp. Yêu cầu bắt buộc là một sinh
viên chỉ đại diện cho một nhóm. Làm thế nào để
chọn đại diện từ mỗi nhóm để đảm bảo yêu cầu
này?
Hãy điền nốt hai hàng cuối để được một hình
vuông Latin hoàn chỉnh.
(b) Hãy chỉ ra rằng: việc điền hàng tiếp theo của
một hình vuông Latin n × n tương đương với
bài toán ghép cặp trên đồ thị hai phần, mỗi
phần gồm n-đỉnh.
(c) Hãy chứng minh rằng luôn tồn tại ghép cặp
trong đồ thị hai phần này và, vậy thì ta luôn
có thể mở rộng một một hình chữ nhật Latin
để thành một Latin square.
(a) Mô hình bài toán lựa chọn đại diện bằng
ghép cặp.
(b) Danh sách đăng ký nhóm của sinh viên cho
thấy rằng không có sinh viên nào là thành
viên của hơn 4 nhóm và mọi nhóm đều có ít
nhất 4 sinh viên. Liệu điều này có đảm bảo
luôn có cách chọn đại diện thích hợp không?
hãy giải thích.
4. Lấy một bộ bài gồm 52 quân. Mỗi quân bài có
một chất và một gía trị. Có bốn chất: Rô, Cơ, Bích,
Nhép; và có 13 giá trị: A, 2, 3, ··· , 10, J,Q, K.
Hãy đề nghị một người bạn xếp bài trên một lưới
gồm 4 hàng và 13 cột. Chị ta có thể để các quân
bài theo cách bất kỳ. Trong bài tập này, bạn sẽ
chứng minh rằng bạn luôn có thể lấy 13 quân bài,
mỗi quân từ một cột trên lưới, sao cho có đủ 13
giá trị.
2. Do số giờ lên lớp bị giảm đi, các sinh viên sẽ có
nhiều thời gian hơn để tham gia vào các câu lạc
bộ sinh viên (CLB); các CLB được đặt dưới sự quản
lý của Hội sinh viên. Mỗi CLB đều muốn có thành
viên đại diện ở trong ban chấp hành của Hội (để
dễ xin tiền tài trợ), nhưng ban chấp hành không
cho phép sinh viên nào đại diện cho hơn một CLB.
(a) Hãy mô hình bài toán này bằng cặp ghép
trên đồ thị hai phần giữa 13 cột và 13 giá
trị.
Sau khi xem hồ sơ, chị chủ tịch Hội thấy rằng:
không có sinh viên nào là thành viên của nhiều
hơn 9 câu lạc bộ, và mọi CLB đều có nhiều hơn 13
thành viên. Liệu điều này đã đủ để đảm bảo luôn
có cách chọn đại diện từ các CLB chưa? Hãy giải
thích.
(b) Chỉ ra rằng mọi nhóm gồm n cột phải chứa ít
nhất n giá trị khác nhau và chứng minh rằng
tồn tại cặp ghép.
5. Các nhà nghiên cứu sau nhiều năm đã chỉ ra 20
đức tính cơ bản của con người: Trung thực, rộng
lượng, trung thành, kiên trì, hoàn thành bài tập
đầy đủ,... Vào đầu khóa học, mỗi sinh viên Khoa
học máy tính đều có đúng 8 trong số 20 đức tính
trên. Hơn nữa tập đức tính cơ bản cho mọi sinh
viên là duy nhất; có nghĩa rằng không có hai sinh
viên nào đã có cùng tập đức tính cơ bản. Các giảng
viên Toán rời rạc phải lựa chọn thêm một đức tính
nữa để đào tạo mỗi sinh viên trong suốt khóa học.
Chứng minh rằng có một cách chọn thêm một đức
tính cho mỗi sinh viên sao cho mỗi sinh viên có
những đức tính khác nhau vào cuối khóa.
phần tử là các số 1, ... , n. Các phần tử phải thỏa
mãn hai ràng buộc: mọi hàng đều chứa đủ các số
1, ... , n theo một thứ tự nào đó, và mọi cột cũng
phải chứa đủ các số 1, ... , n theo thứ tự nào đó.
Ví dụ, bảng dưới đây là một hình vuông Latin 4 ×
4:
1
3
2
4
2
4
1
3
3
2
4
1
4
1
3
2
6. (Bài toán ’harem’) Xét một tập chàng trai B, và giả
sử mỗi chàng trai trong B đều mong muốn cưới
nhiều hơn một trong số các bạn gái của anh ta.
Tìm một điều kiện cần và đủ để bài toán harem
có lời giải.
(a) Dưới đây là ba hàng của một hình vuông
Latin 5 × 5 :
1Thuật ngữ Latin bắt nguồn từ Euler. Ông đã dùng tập ký tự
Latin cho các phần tử của bảng.
1 trang
15420
Free
Bạn đang xem tài liệu "Bài tập Toán rời rạc - Phần: Cặp ghép", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_tap_toan_roi_rac_phan_cap_ghep.pdf
