Problem
COM-B2-M08-P011 Intervals of Days
#11
★★★☆☆ Level 3 of 5
Each of \(n\) talks may be scheduled on certain allowed days. For any \(k\) talks, the union of their allowed days contains at least \(k\) days. Prove that all talks can be assigned distinct days.
This is exactly Hall's condition.
Build a bipartite graph: talks on the left, days on the right, and an edge means the talk may be scheduled on that day. The condition says that for every set \(S\) of talks, the neighbour set of days has size at least \(|S|\). By Hall's theorem, there is a matching covering all talks. It gives the schedule.
A word problem requiring direct graph translation.