## Rig the election with math!

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]

## The Traitorous Generals

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]