TAOCP 7.2.2.1 Exercise 69

Section 7.2.2.1: Dancing Links

Exercise 69. ▶ [30] [30] Diagram (i) below shows the 81 communities of Bitland, and their nine electoral districts. The voters in each community are either Big-Endian (B) or Little-Endian (L). Each district has a representative in Bitland's parliament, based on a majority vote.

Notice that there are five Ls and four Bs in every district, hence the parliament is 100% Little-Endian. Everybody agrees that this is unfair. So you have been hired as a computer consultant, to engineer the redistricting.

A rich bigwig secretly offers to pay you a truckload of money if you get the best possible deal for his side. You could gerrymander the districts as in diagram (ii), thereby obtaining seven Big-Endian seats. But that would be too blatantly biased.

Show that seven wins for B are actually obtainable with nine districts that do respect the local neighborhoods of Bitland quite decently, because each of them is a convex nondomino that fits in a $4 \times 4$ square (see exercise 68).

Verified: no
Solve time: 2m01s

---

Setup

Exercise 7.2.2.1.69 depends on the two diagrams in the statement, because the construction must use the actual arrangement of the 81 communities and their B/L labels. The required proof is existential: we must exhibit nine districts, each a convex nondomino fitting inside a $4 \times 4$ square, and show that seven of those districts have a Big-Endian majority.

The supplied text includes the description of the diagrams but does not include the contents of diagram (i), namely the locations of the 81 communities and their labels. Without that information, the majority counts of candidate districts cannot be computed.

Solution

A complete solution requires the following data from diagram (i):

1. The $9 \times 9$ array of community labels, with each entry equal to either $B$ or $L$.
2. The precise interpretation of adjacency used for the allowed district shapes.
3. The numbering or coordinates of the cells, so that the nine convex nondominoes can be specified.

Given that data, the construction would proceed by selecting nine disjoint sets of cells $D_1,\ldots,D_9$ satisfying:

$|D_k|=9$

for every $k$, because the districts partition the $81$ communities, and each $D_k$ must be a convex nondomino contained in some $4 \times 4$ bounding square.

For each district $D_k$, the number of Big-Endian communities would be computed as

$B(D_k)=\sum_{x\in D_k}[x\text{ is labeled }B].$

The district gives a Big-Endian seat exactly when

$B(D_k)> \frac{|D_k|}{2}=\frac92,$

so the condition is

$B(D_k)\ge5.$

The final construction must therefore exhibit nine admissible districts for which at least seven indices $k$ satisfy

$B(D_k)\ge5.$

The proof of optimality is not requested in this exercise; only the existence of a locally reasonable redistricting with seven Big-Endian seats must be demonstrated.

Verification

The necessary verification cannot be performed from the supplied information, because the seven winning districts and their vote totals depend on the missing diagram data. Any claimed list of districts or majority counts without the diagram would introduce information not contained in the problem statement.

Notes

Please provide the image or a transcription of diagram (i) and, if available, diagram (ii). With the $9 \times 9$ label array, the complete construction and all nine district vote counts can be derived explicitly.