4
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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 44$ are here: https://oeis.org/A365271

8x8:

enter image description here

9x9:

enter image description here

10x10:

enter image description here

11x11:

enter image description here

12x12:

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Bubbler
    Commented Jul 12 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.