pigeonhole principle - Book Proofs

This Riddler problem is about gerrymandering. How to redraw borders to sway a vote one way or another.

Below is a rough approximation of Colorado’s voter preferences, based on county-level results from the 2012 presidential election, in a 14-by-10 grid. Colorado has seven districts, so each would have 20 voters in this model. In each district, the party with the most votes will win. The districts must be non-overlapping and contiguous (that is, each square in a district must share an edge with at least one other square in the district). What is the most districts that the Red Party could win? What about the Blue Party? (Assume ties within a district are considered wins for the party of your choice.)

Two boards are provided, a test 5×5 grid and the larger 14×10 grid:

Here is a first solution, using some simple logic and intuition:
[Show Solution]

And here is a computational approach, using integer programming:
[Show Solution]

One way to solve this problem numerically is to formulate it as an integer programming problem. The benefit is that it will always find an optimal solution eventually, but the downside is that it may take awhile. My code solved the 5-by-5 case in a matter of seconds, but the 14-by-10 case computed for over 12 hours with no solution, so I gave up. Of course, it may be possible to solve the larger case using this method, but it would require either a more efficient model or a faster computer!

The idea is to think of the grid cells as nodes of a directed graph. We place an edge between two nodes (one in each direction) if the cells are adjacent. Number the cells $1,2,\dots,C$ and number the edges $1,2,\dots,E$. Define the adjacency matrix $A \in \{0,1\}^{C\times C}$, the incidence matrix $B\in \{0,1\}^{C\times E}$, and the vector $v\in\{0,1\}^C$ as follows:
\begin{align}
A_{ij} &= \begin{cases}
1&\text{if there is an edge from cell }i\text{ to cell }j\\
0&\text{otherwise}
\end{cases}\\[2mm]
B_{ij} &= \begin{cases}
1&\text{if edge }j\text{ starts at cell }i\\
-1&\text{if edge }j\text{ ends at cell }i\\
0&\text{otherwise}
\end{cases}\\[2mm]
v_i &= \begin{cases}
1&\text{if cell }i\text{ is blue}\\
0&\text{if cell }i\text{ is red}
\end{cases}
\end{align}Suppose our districts are numbered $1,2,\dots,D$. The first set of variables in our model are $x\in\{0,1\}^{C\times D}$ and $w\in\{0,1\}^D$ and they represent:
\begin{align}
x_{ij} &= \begin{cases}
1&\text{if cell }i\text{ belongs to district }j\\
0&\text{otherwise}
\end{cases}\\[2mm]
w_j &= \begin{cases}
1&\text{if district }j\text{ is a winner}\\
0&\text{otherwise}
\end{cases}
\end{align}We then have several intuitive constraints which we can encode algebraically as linear constraint for our model:

Each cell belongs to exactly one district:
\[\sum_{j=1}^D x_{ij} = 1\quad\text{ for }i=1,\dots,C\]
Each district contains exactly $S$ cells:
\[\sum_{i=1}^C x_{ij} = S\quad\text{ for }j=1,\dots,D\]
A district wins if and only if there are at least $W$ votes:
\[W w_j \le \sum_{i=1}^C x_{ij} v_i \le (S+1)w_j + (W-1)\quad\text{ for }j=1,\dots,D\]

Unfortunately, these constraints alone don’t force the districts to be contiguous. For this, we must make use of the graph structure. The idea is to set it up as a flow problem. Imagine two new nodes, a universal source and a universal sink. There are edges from the source to every cell, and edges from every cell to the sink. Then imagine a flow that propagates along the edges. The source provides $S$ units of flow (at most one unit of flow per source edge), the sink must accept $S$ units of flow (and it must all occur on a single sink edge), and each cell in the graph conserves flow. These combined constraints ensure that selected cells are path-connected in the graph, which means they are contiguous in the grid. The variables we’ll use are $f \in \mathbb{Z}^{E\times D}$ and $f^\text{out} \in \{0,1\}^{C\times D}$, defined as:
\begin{align}
f_{ij} &= \begin{cases}
1&\text{if edge }i\text{ is used in the flow for district }j\\
0&\text{otherwise}
\end{cases}\\[2mm]
f^\text{out}_{ij} &= \begin{cases}
1&\text{if cell }i\text{ contains the flow to the sink for district }j\\
0&\text{otherwise}
\end{cases}
\end{align}We then have the constraints:

Each edge has a flow capacity of $S$:
\[
0 \le f_{kj} \le S\quad\text{ for }k=1,\dots,E\text{ and }j=1,\dots,D
\]
At most one sink edge is used to return the flow:
\[
\sum_{i=1}^C f^\text{out}_{ij} = 1\quad\text{ for }j=1,\dots,D
\]
Flow is conserved at each cell (including flow involving source and sink)
\[
\sum_{k=1}^E B_{ik}f_{kj} + S f_{ij} = x_{ij}\quad\text{ for }i=1,\dots,C\text{ and }j=1,\dots,D
\]
If an edge is used, the associated cells must be selected
\[
x_{ij} \ge \alpha \sum_{k=1}^E |B_{ik}| f_{kj}\quad\text{ for }i=1,\dots,C\text{ and }j=1,\dots,D
\]

In the final constraint, $\alpha$ is a constant that must be chosen sufficiently small to be less than 1 for any amount of flow. Since there are at most 6 active edge (4 internal, 1 source, 1 sink), it suffices to choose $\alpha < \frac{1}{5S+1}$.

Finally, our objective function is to minimize (or maximize) the total number of winning districts. In other words, $w_1+\dots+w_D$. That’s it!

I used IJulia, JuMP, and Gurobi to solve the integer programs, and on my laptop it took on the order of seconds for the 5×5 case. Unfortunately, the 14×10 case ran for over 12 hours without terminating. So it seems my approach might not be viable for large versions of this problem. The solution my code found for the 5×5 was:
If you’re interested in seeing my code in full detail, you can view/download the notebook here.

This Riddler problem is a logic puzzle about liars and truth-tellers.

You are the emperor of Byzantium (lucky you!) and you have N generals working for you. You know that more than half of your generals are loyal, and the rest are traitors. You can ask any general about the loyalty of any other general: If the general you ask is loyal, he will answer correctly, but if he is a traitor he can answer however he likes. Your goal is to find one general you are absolutely certain is loyal while asking the fewest possible questions.

What is the minimum number of questions (in terms of N) that will guarantee a solution, and what strategy produces it?

There is a problem in cryptography known as the Byzantine Generals Problem, which has to do with achieving consensus in the presence of traitors that can sabotage communications. The Riddler problem above also involves liars and truth-tellers, but it’s a very different problem.

The following is adapted from a comment by Guy Moore. A similar solution that obtains the same final result was also found by Dmytro Taranovsky. Thank you both for your insights!

[Show Solution]

The $N$ generals have the property that there is a loyal majority. This solution efficiently eliminates generals such that the remaining group of generals preserves the loyalty majority property. The strategy is:

If there is an even number of generals, eliminate one of the generals (doesn’t matter which).
If there is an odd number of generals, set one general aside. Pair up the rest of the generals and for each pair, ask the first general if the second one is a traitor.
- If the first general says the other is a traitor, eliminate both generals.
- If the first general says the other is loyal, eliminate the first general and keep the second.
If we kept an odd number of generals, eliminate the general that was set aside. Otherwise, re-include the general that was set aside.
If there is only one general left, this general is loyal and we may stop. Otherwise, return to the first step and repeat the process with the generals that are left.

Why does this work?

At each step, the loyalty majority property is preserved. To see why, let’s examine each case.

If the first general says the second is a traitor, they cannot both be loyal. Therefore, by eliminating both, we eliminate at least as many traitors as loyal generals.
If the first general says the second is loyal, we eliminate the first one. If the general that remains is a traitor, then both of them were traitors. This can happen for at most half of the pairs, since otherwise there would be a majority of traitors. If it happens for exactly half of the pairs, then the general we set aside must be loyal and so by re-including the general we set aside we retain loyal majority.
If there is only one general remaining, then the loyalty majority implies that this general must be loyal.

How well does the strategy perform?

If we have $k$ generals, we ask $\left\lfloor{\frac{k-1}{2}}\right\rfloor$ questions. In the worst case, each question leads to only one elimination. We also re-include the general we set aside depending on parity. So the number of generals remaining in the next round is:

\[
\begin{cases}
\left\lfloor\frac{k-1}{2}\right\rfloor & \text{if }k\text{ is odd}\\
\left\lfloor\frac{k-1}{2}\right\rfloor + 1 & \text{if }k\text{ is even}
\end{cases}
\]

This is equivalent to

\[
1 + 2\left\lfloor\frac{1}{2}\left\lfloor\frac{k-1}{2}\right\rfloor\right\rfloor = 1 + 2\left\lfloor\frac{k-1}{4}\right\rfloor
\]

We can make this simplification thanks to the nested division property of the floor function. So if $q(k)$ is the maximum number of questions required, we have the recursion:

\begin{align}
q(1) &= 0 \\
q(k) &= \left\lfloor{\tfrac{k-1}{2}}\right\rfloor + q\left( 1 + 2\left\lfloor{\tfrac{k-1}{4}}\right\rfloor \right)
\end{align}

If we define $f(k) = k-q(k+1)$ and do some rearrangements, we can write the following recursion for $f(k)$:

\begin{align}
f(0) &= 0 \\
f(k) &= k- \left\lfloor{\tfrac{k}{2}}\right\rfloor- 2\left\lfloor{\tfrac{k}{4}}\right\rfloor + f\left(1+2\left\lfloor{\tfrac{k}{4}}\right\rfloor\right)
\end{align}

It turns out that $f(k)$ is the number of 1’s in the binary representation of $k.$ Or, equivalently, $f(k)$ is the sum of the binary digits of $k$. I’ll omit the derivation, but you can work it out by writing $k$ in binary and noting that each operation does something simple to the digits. For example, if $x = abcde_2$ then $\lfloor x/2 \rfloor = abcd_2$. Therefore, we conclude that if there are $N$ generals, the number of questions required in order to ensure we can select a loyal general is:

$\displaystyle
q(N) = N-1-f(N-1)
$

where $f(k)$ is the number of 1’s in the binary representation of $k.$ Here is a plot showing the questions needed as a function of the number of generals.

We always require slightly fewer questions that there are generals, and we can bound the number of questions as:

\[
N-1-\log_2(N) \le q(N) \le N-2
\]

Tag: pigeonhole principle

Rig the election with math!

The Traitorous Generals

Why does this work?

How well does the strategy perform?