A365271 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, 3, 4, 6, 8, 11, 14, 16, 20, 24, 28, 32, 36, 42, 48, 54, 60, 66, 72, 80, 88, 96, 104, 112, 120, 130, 140, 150, 158, 168, 180, 192, 204, 215, 226, 238, 252, 264, 277, 289, 306, 320, 336, 351

Offset: 1

Author

Andrew Parkinson, Aug 30 2023

Keywords

• nonn
• more
• hard

Comments

Developed from the Destroying Democracy Puzzle created by Gordon Hamilton.

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.

Examples

			For n=4, a(4)=6:
.
              +-----------+---+
  Region A -->| X   X   O | O |
              +-----------+   |
  Region B -->| X   X   O | O |
              +-----------+   |<-- Region E
  Region C -->| X   X   O | O |
              +-----------+   |
  Region D -->| O   O   O | O |
              +-----------+---+
.
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.
See the Hamilton link for more examples.
		

Links

• Gordon Hamilton, Destroying Democracy!, MathPickle, 2020.
• Andrew Parkinson and Rob Pratt, Additional and conjectured terms to a(61).

Crossrefs

Cf. A341319, A172477.

Formula

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

Extensions

a(29)-a(44) obtained via integer linear programming by Rob Pratt, Jul 26 2024