This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
Problem 69 was about separating \(n\) prisoners, with \(m\) pairs of enemies among them, into 2 cells, so that the number of enemy pairs within either cell would be at most \(m/2\). We saw a deterministic way to do this, and a faster randomized algorithm to do the same thing.
Come up with an example of prisoners and enemy relationships to show that the deterministic algorithm from before (moving prisoners to another cell as long as they have fewer enemies in that cell) does not always find the optimal solution.
Specifically, you need to come up with a set of prisoners, a listing of enemy pairs, and a way of grouping them in two cells such that moving any one prisoner to the other cell would make things worse. Then you show a different grouping of the same prisoners into two cells that is better (fewer enemies within the cells).