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.

For a \(1 \times n\) grid:

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.\)