Problem
COM-B2-M08-P016 Forbidden Days
There are \(n\) exams and \(n\) days. Each exam is forbidden on at most one day, and each day is forbidden for at most one exam. Prove that the exams can be assigned to distinct days respecting the restrictions.
Check Hall's condition separately for one exam and for two or more exams.
Build a bipartite graph: an exam is joined to a day if it may be held on that day. We check Hall's condition.
For one exam, at least \(n-1\) days are available, and for \(n\ge2\) this is at least \(1\). If \(k\ge2\) exams are chosen, then every day is available to at least one of them: a day can be forbidden for at most one exam. Hence the union of available days is all \(n\) days, and \(n\ge k\).
Hall's condition holds for every set of exams. Therefore a schedule with distinct days exists.
A good problem on careful case checking in Hall's condition.