Bài tập Toán rời rạc - Bài 7

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? (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. 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. 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. 3. Một hình vuông Latin1 là một bảng n × n với các 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 2 3 4 3 4 2 1 2 1 4 3 4 3 1 2 (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. 2 4 5 3 1 4 1 3 2 5 3 2 1 5 4 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. 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ị. (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ị. (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. 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.