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