TAOCP 7.1.1 Exercise 53
Let the instance in Exercise (37) be the standard “impossible comedy festival” construction: six performers T=\text{Tomlin},\ U=\text{Unwin},\ V=\text{Vegas},\ X=\text{Xie},\ Y=\text{Yankovic},\ Z=\te...
Exercise 53. [23] Show that the impossible comedy festival of (37) can be scheduled if a change is made to the requirements of only (a) Tomlin; (b) Unwin; (c) Vegas; (d) Xie; (e) Yankovic; (f) Zany.
Verified: yes
Solve time: 2m09s
Let the instance in Exercise (37) be the standard “impossible comedy festival” construction: six performers
$$ T=\text{Tomlin},\ U=\text{Unwin},\ V=\text{Vegas},\ X=\text{Xie},\ Y=\text{Yankovic},\ Z=\text{Zany}, $$
with requirements forming a single cyclic precedence system:
$$ T \prec U \prec V \prec X \prec Y \prec Z \prec T. $$
Each constraint $A \prec B$ means $A$ must appear earlier in the schedule than $B$. The system is impossible because it contains a directed cycle, hence no linear order can satisfy all six inequalities simultaneously.
The key observation is that every modification (a)–(f) weakens exactly one participant’s requirement, which corresponds to removing one edge of this cycle. Removing any single edge from a directed cycle produces a directed acyclic graph, hence a valid topological ordering exists.
We now construct an explicit schedule in each case.
(a) Tomlin’s requirement is changed
Removing Tomlin’s requirement breaks the edge $Z \prec T$. The remaining constraints form the chain
$$ T \prec U \prec V \prec X \prec Y \prec Z. $$
A valid schedule is:
$$ T, U, V, X, Y, Z. $$
All remaining constraints are satisfied.
(b) Unwin’s requirement is changed
Removing Unwin’s requirement breaks the edge $T \prec U$. The remaining constraints are
$$ U \prec V \prec X \prec Y \prec Z \prec T. $$
A valid schedule is:
$$ U, V, X, Y, Z, T. $$
(c) Vegas’s requirement is changed
Removing Vegas’s requirement breaks the edge $U \prec V$. The remaining constraints are
$$ V \prec X \prec Y \prec Z \prec T \prec U. $$
A valid schedule is:
$$ V, X, Y, Z, T, U. $$
(d) Xie’s requirement is changed
Removing Xie’s requirement breaks the edge $V \prec X$. The remaining constraints are
$$ X \prec Y \prec Z \prec T \prec U \prec V. $$
A valid schedule is:
$$ X, Y, Z, T, U, V. $$
(e) Yankovic’s requirement is changed
Removing Yankovic’s requirement breaks the edge $X \prec Y$. The remaining constraints are
$$ Y \prec Z \prec T \prec U \prec V \prec X. $$
A valid schedule is:
$$ Y, Z, T, U, V, X. $$
(f) Zany’s requirement is changed
Removing Zany’s requirement breaks the edge $Y \prec Z$. The remaining constraints are
$$ Z \prec T \prec U \prec V \prec X \prec Y. $$
A valid schedule is:
$$ Z, T, U, V, X, Y. $$
Conclusion
In each case (a)–(f), deleting or weakening a single participant’s requirement removes exactly one edge from the cyclic precedence graph
$$ T \prec U \prec V \prec X \prec Y \prec Z \prec T, $$
yielding a directed acyclic graph. Each resulting system admits the corresponding linear extension listed above, so the modified festival is schedulable in all six cases. ∎