Để biết có thể thi hết các môn trong một ngày hay không, ta cần phân phối các môn tự chọn vào hai ca còn lại (ca 2 và ca 3) sao cho:
- Mỗi học sinh trong một tổ hợp đều thi được cả hai môn tự chọn, tức là hai môn không được thi cùng ca.
- Tất cả các môn trong các tổ hợp đều được xếp lịch thi phù hợp.
- Số ca chỉ có 2 ca cho môn tự chọn.
Các tổ hợp môn học sinh chọn:
- Toán, Văn + Vật lý, Hóa
- Toán, Văn + Vật lý, Anh
- Toán, Văn + Vật lý, Sử
- Toán, Văn + Hóa, Sinh
- Toán, Văn + Hóa, GDCD
- Toán, Văn + Hóa, Anh
- Toán, Văn + Sinh, GDCD
- Toán, Văn + Sử, Anh
=> Các môn tự chọn xuất hiện: Vật lý, Hóa, Anh, Sử, Sinh, GDCD
Bước 1: Lập đồ thị hai màu (coloring graph)
Xem các môn như đỉnh, nối hai môn nếu chúng xuất hiện cùng tổ hợp ⇒ phải thi ở hai ca khác nhau.
Ta có các cạnh nối giữa các môn sau:
- Vật lý – Hóa
- Vật lý – Anh
- Vật lý – Sử
- Hóa – Sinh
- Hóa – GDCD
- Hóa – Anh
- Sinh – GDCD
- Sử – Anh
Tập các đỉnh: {Lý, Hóa, Anh, Sử, Sinh, GDCD}
Bước 2: Kiểm tra xem có thể tô màu 2 màu không (tức chia làm 2 ca)
Nếu đồ thị là đồ thị hai phần (bipartite), thì ta có thể chia các môn thành 2 ca sao cho không có cạnh nào nối hai đỉnh cùng màu ⇒ Không có học sinh nào bị trùng ca hai môn.
Tiến hành tô màu:
- Chọn Vật lý (Lý) là màu 1
- Hóa, Anh, Sử → màu 2
- Hóa nối với Sinh, GDCD ⇒ Sinh, GDCD → màu 1
- Sử nối với Anh (cùng màu 2) ⇒ OK
- Anh nối với Hóa và Sử (cùng màu 2) ⇒ OK
- Sinh và GDCD nối nhau ⇒ cùng màu 1 → vi phạm (2 đỉnh nối nhau có cùng màu)
→ Đồ thị không phải hai phần ⇒ Không thể chia 6 môn vào 2 ca thi mà đảm bảo không trùng lịch cho tất cả học sinh
Kết luận:
Không thể thi hết tất cả các môn trong một ngày với 3 ca như mô tả, vì không thể chia các môn tự chọn vào 2 ca mà đảm bảo không học sinh nào bị trùng ca hai môn tự chọn.
