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,2

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.

Links

Table of n, a(n) for n=1..44.

Gordon Hamilton, Destroying Democracy!, MathPickle, 2020.

Andrew Parkinson and Rob Pratt, Additional and conjectured terms to a(61).

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

Example

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.

Crossrefs

Cf. A341319, A172477.

Sequence in context: A079401 A156040 A325172 * A242254 A107770 A067054

Adjacent sequences: A365268 A365269 A365270 * A365272 A365273 A365274

Keyword

nonn,more,hard

Author

Andrew Parkinson, Aug 30 2023

Extensions

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

Status

approved