login
Minimum number of shaded squares needed on an n X n grid divided into rectangular regions so that more than half of the regions have more than half of their squares shaded and the area of the smallest region is more than half that of the largest region.
1

%I #75 Jul 27 2024 12:17:58

%S 1,3,4,6,8,11,14,16,20,24,28,32,36,42,48,54,60,66,72,80,88,96,104,112,

%T 120,130,140,150,158,168,180,192,204,215,226,238,252,264,277,289,306,

%U 320,336,351

%N Minimum number of shaded squares needed on an n X n grid divided into rectangular regions so that more than half of the regions have more than half of their squares shaded and the area of the smallest region is more than half that of the largest region.

%C Developed from the Destroying Democracy Puzzle created by Gordon Hamilton.

%C To achieve a minimum, we need there to be x regions of area >= 2m-1 and (x-1) regions of area <= 4m-3 and m squares shaded in each of the x smaller regions. It can be shown that it is sufficient to only consider an odd number (2x-1) of regions. A weak lower bound is given in the formula section. Exhaustive searches lead to a stronger lower bound on each term, a(n), by identifying values of x and m which enable us to apportion the n^2 grid squares into rectangular regions with side lengths <= n. We then confirm each term by finding an actual configuration of regions that fits the n X n grid.

%H Gordon Hamilton, <a href="https://mathpickle.com/project/democracy/">Destroying Democracy!</a>, MathPickle, 2020.

%H Andrew Parkinson and Rob Pratt, <a href="/A365271/a365271_2.txt">Additional and conjectured terms to a(61)</a>.

%F A weak lower bound on a(n) is a(n) > n^2/6. (The area of the smaller regions with more than half of their squares shaded is more than half of the area of the larger regions, so the area of the smaller regions is more than one third of the total grid; therefore the number of shaded squares is greater than one sixth of the number of grid squares.)

%e For n=4, a(4)=6:

%e .

%e +-----------+---+

%e Region A -->| X X O | O |

%e +-----------+ |

%e Region B -->| X X O | O |

%e +-----------+ |<-- Region E

%e Region C -->| X X O | O |

%e +-----------+ |

%e Region D -->| O O O | O |

%e +-----------+---+

%e .

%e The diagram shows the 4 X 4 grid divided into 5 regions. In the 3 regions A, B and C (more than half of the regions), more than half of the squares within each region (2 out of 3) are shaded (X). Of the 16 squares, only 6 (the minimum possible) are shaded; therefore, a(4)=6.

%e See the Hamilton link for more examples.

%Y Cf. A341319, A172477.

%K nonn,more,hard

%O 1,2

%A _Andrew Parkinson_, Aug 30 2023

%E a(29)-a(44) obtained via integer linear programming by _Rob Pratt_, Jul 26 2024