Đây là bài toán về việc xếp lịch thi tốt nghiệp THPT thử cho một trường cấp 3. Tóm tắt đề bài: * Môn thi tốt nghiệp 2025: Học sinh thi 4 môn: 2 môn bắt buộc (Ngữ Văn, Toán) và 2 môn tự chọn trong số các môn còn lại lớp 12 (Ngoại ngữ, Sử, Lý, Hóa, Sinh, Địa, GD kinh tế & pháp luật, Tin học, Công nghệ). * Lịch thi thử của trường: Thi trong 1 ngày, chia 3 ca: * Ca 1: Toán và Văn. * Ca 2 và Ca 3: Hai môn tự chọn còn lại của học sinh. * Các tổ hợp học sinh đã chọn (tại trường này): * Toán, Văn, Lý, Hóa * Toán, Văn, Lý, Anh * Toán, Văn, Lý, Sử * Toán, Văn, Hóa, Sinh * Toán, Văn, Hóa, GD KT&PL * Toán, Văn, Hóa, Anh * Toán, Văn, Sinh, GD KT&PL * Toán, Văn, Sử, Anh * Câu hỏi: Có thể thi hết các môn trong một ngày được không? Vì sao? Biết rằng không có học sinh nào chọn tổ hợp có cả Tin học và Công nghệ. Phân tích và Giải đáp: * Các môn tự chọn cần xếp lịch: Dựa trên các tổ hợp học sinh đã chọn, các môn tự chọn cần được xếp vào Ca 2 và Ca 3 là: Vật lý, Hóa học, Ngoại ngữ (Anh), Lịch sử, Sinh học, Giáo dục kinh tế và pháp luật. (Tổng cộng 6 môn tự chọn). * Nguyên tắc xếp lịch: Hai môn tự chọn mà có học sinh chọn thi cùng nhau (trong cùng một tổ hợp) thì phải được xếp vào 2 ca thi khác nhau (một môn ở Ca 2, một môn ở Ca 3). * Tìm các cặp môn xung đột: * Lý và Hóa (tổ hợp 1) -> Phải khác ca. * Lý và Anh (tổ hợp 2) -> Phải khác ca. * Lý và Sử (tổ hợp 3) -> Phải khác ca. * Hóa và Sinh (tổ hợp 4) -> Phải khác ca. * Hóa và GD KT&PL (tổ hợp 5) -> Phải khác ca. * Hóa và Anh (tổ hợp 6) -> Phải khác ca. * Sinh và GD KT&PL (tổ hợp 7) -> Phải khác ca. * Sử và Anh (tổ hợp 8) -> Phải khác ca. * Kiểm tra khả năng xếp lịch: * Giả sử xếp môn Vật lý vào Ca 2. * Vì (Lý, Hóa), (Lý, Anh), (Lý, Sử) xung đột -> Hóa, Anh, Sử phải được xếp vào Ca 3. * Bây giờ xét Ca 3. Ca này đã có Hóa, Anh, Sử. Tuy nhiên, ta thấy có tổ hợp (Hóa, Anh) và (Sử, Anh). Điều này có nghĩa là Hóa và Anh phải khác ca, Sử và Anh cũng phải khác ca. Nhưng chúng lại đang bị buộc phải xếp chung vào Ca 3 (vì cùng xung đột với Lý ở Ca 2). Mâu thuẫn! * Tương tự, Hóa và Anh cũng không thể cùng ở Ca 3 vì có học sinh chọn cả hai môn này. * Kết luận: * Không thể thi hết các môn trong một ngày (với 3 ca như mô tả). * Vì sao: Do có những cặp môn tự chọn mà học sinh đăng ký thi cùng nhau, tạo ra sự xung đột lịch thi không thể giải quyết chỉ với 2 ca thi tự chọn (Ca 2 và Ca 3). Cụ thể, có ít nhất 3 môn là Vật lý, Hóa học và Ngoại ngữ (Anh) mà trong đó, bất kỳ cặp nào cũng có học sinh chọn thi (Lý-Hóa, Lý-Anh, Hóa-Anh). Không thể xếp 3 môn này vào 2 ca thi mà không bị trùng lịch cho một nhóm học sinh nào đó. Việc không có học sinh nào chọn Tin học và Công nghệ không ảnh hưởng đến kết luận trên, vì sự xung đột đã xảy ra với các môn Vật lý, Hóa học và Ngoại ngữ (Anh).