# Destroying Democracy

There is a square grid of people and two political parties: Red and Yellow. The grid is split into districts, with the following rules:

• All districts must be rectangles
• Each voter must be in exactly 1 district
• No district can contain twice or more votes as another district. For example, if there is a district with 5 people, there can be no district with fewer than 3 or more than 9 people.

A party wins a district when they have more than half the votes in that district. The winner of an election is the party that wins more districts. What is the minimum number of Red voters needed to win the election for square grids of size from 3x3 to 12x12?

Source: https://mathpickle.com/project/democracy/ (not all the bounds are the best possible).

Via integer linear programming, I found the following minimum values for $$n \times n$$ grids:

$$\begin{matrix} n & \min \\ \hline 3 & 4 \\ 4 & 6 \\ 5 & 8 \\ 6 & 11 \\ 7 & 14 \\ 8 & 16 \\ 9 & 20 \\ 10 & 24 \\ 11 & 28 \\ 12 & 32 \end{matrix}$$

Minimum values for $$n \le 28$$ are here: https://oeis.org/A365271

8x8:

9x9:

10x10:

11x11:

12x12:

• I was about to post the same answers for 8, 9, and 10 found by hand. For 11 I correctly guessed the size of the small districts but couldn't fit seven 1x7s and six rectangles of area 12. For 12 I didn't bother to check small districts that large, but if I did it'd be pretty easy to find the tiling. Commented Jul 12 at 2:34