# Destroying Democracy!

Start by reading this. I would also suggest watching this, then this. Please add any thoughts you may have on this puzzle to the Discord.

Rules:

1. All regions must be rectangular.
2. Each voter must be in exactly one region.
3. No region may be twice as large, or larger, than the smallest region.

Observations:

The difficulty is not placing the faces, the difficulty is finding the regions.

If we have $$k$$ regions, the smallest $$\lfloor k/2 \rfloor + 1$$ regions should be red-winning, and the rest yellow-winning.

Every solution can be reflected and rotated, by the symmetries of the square, to yield other solutions. The square has 8 symmetries, so only 1 solution from those 8 should be considered.

If you have a solution where a region is won by yellow, then all faces within said region should be yellow.

If you have a solution where a region is won by red, just over half of the faces should be red. For example, if you have a region with 5 faces won by red, then 3 of those should be red, and 2 yellow.

No red-winning region can consist of fewer than 2 red faces.

If we have a region of 4 faces, 3 of them need to be red, for red to win. But if we have a region of 5 faces, we also need just 3 of them to be red, for red to win.

Question:

Should red-winning regions always have an odd number of faces?

Simple upper bound:

Call the number of rows $$r,$$ and the number of columns $$c.$$ Suppose each row is a region. Then the number of red faces per row must be $$\lfloor c/2 \rfloor + 1,$$ just over half the number of columns. We need to win just over half the rows, which is $$\lfloor r/2 \rfloor + 1$$ of them. So the maximum number of red faces we need, for an $$r \times c$$ region, is (\lfloor r/2 \rfloor + 1)(\lfloor c/2 \rfloor + 1).\) This is a very crude upper bound, but still, it greatly reduces the search space from what it was.

Questions:

Can this algorithm be improved?

Is there another algorithm just as simple, that provides a better upper bound?

Can an algorithm be found that provides a decent lower bound for the number of red faces?

What is the minimum number of red faces for special cases? For example, what about a $$1 \times n$$ grid? A $$2 \times n$$ grid?

Best known solutions:

In the list below, the number following the dimensions of each grid, is the smallest number of red faces, for which a solution is currently known.

• 1x1: 1
• 2x2: 3
• 3x3: 4
• 4x4: 6
• 5x5: 8
• 6x6: 11
• 7x7: 14
• 8x8: 18
• 9x9: 21
• 10x10: 25

For a $$1 \times n$$ grid:

• 1x1: 1
• 1x2-3: 2
• 1x4-5: 3
• 1x6-9: 4
• 1x7-11: 4
• 1x12-13: 5
• 1x14-19: 6
• 1x20-21: 7
• 1x22-27: 8

Observations:

For $$1 \times n$$ grids, given a solution with an even number of regions, we can transform it into a solution with an odd number of regions. If there are an even number of regions, there must be p yellow-winning regions, and $$p + 2$$ red-winning regions. Select one of these surplus red-winning regions for removal. We must redistribute its $$k + 1$$ red faces, and $$k$$ yellow faces. We can relocate $$k$$ pairs of red and yellow faces to red-winning regions, until just 1 red face remains. We can relocate this final red face to any red-winning region.

For each $$1 \times n$$ grid, there may be more than 1 optimal solution. For example, $$1 \times 27$$ has at least two optimal solutions. Let X denote red, and O denote yellow. I will give regions as rows, but remember, these should be mentally flattened into $$1 \times n$$ strings:

Solution 1:

XXXXOOO
XXXXOOO
OOOOOOOOOOOOO

$$7 \cdot 2 + 13 = 27$$

Solution 2:

XXO
XXO
XXO
XXO
OOOOO
OOOOO
OOOOO

$$3 \cdot 4 + 5 \cdot 3 = 12 + 15 = 27$$

Conjecture:

One way to find the maximum $$n,$$ for a $$1 \times n$$ grid, given a fixed number of red faces $$R,$$ can be obtained by distributing the $$R$$ red faces as evenly as possibly into some number of $$k \ge 2$$ red-winning regions. Call the area of the smallest red-winning region $$A.$$ Note that there may be more than one smallest red-winning region, depending on how equally we can distribute the red faces. Then make $$k - 1$$ yellow winning regions, each having area $$2A - 1.$$ Further, it doesn't matter how many red-winning regions you make, it only matters that they are distributed as equally as possible. For example, if I have 6 red faces to distribute, I can do either

XXXO
XXXO

or

XXO
XXO
XXO

Notice that after creating the yellow-winning regions, for each of the above cases, I get the same maximum number of faces either way. If I had 7 red faces to distribute, then my options are

XXXOO
XXXXOOO

or

XXO
XXO
XXXOO

Again, after creating the yellow-winning regions for both cases, you will see you get the same maximum number of faces. If this strategy truly provides a maximum, then we can find the maximum for $$R \ge 2$$ by doing the following: Put $$\lfloor R/2 \rfloor$$ red faces into the 1st red-winning region, and $$\lceil R/2 \rceil$$ into the 2nd red-winning region. The first red-winning region will thus have area $$2\lfloor R/2 \rfloor - 1.$$ The second red-winning region will have area $$2\lceil R/2 \rceil - 1.$$ The third region must be yellow-winning, and have area $$2\left(2\lfloor R/2 \rfloor\right) - 1.$$ The sum of these three areas, listed again below, for convenience, gives us the maximum $$n$$ for which a $$1 \times n$$ grid can be won given $$R$$ red faces.

\begin{align} A_1 &= 2\lfloor R/2 \rfloor - 1 \\[1em] A_2 &= 2\lceil R/2 \rceil - 1 \\[1em] A_3 &= 2A_1 - 1 \\[1em] &= 2\left(2\lfloor R/2 \rfloor - 1\right) - 1 \\[1em] &= 4 \lfloor R/2 \rfloor - 3 \\[1em] n &= A_1 + A_2 + A_3 \end{align}

Remember that this formula only works for $$R \ge 2,$$ but it's obvious that if $$R = 1,$$ then $$n = 1,$$ and so we can now find the maximum $$n$$ for any positive number of red faces $$R.$$