cp's OEIS Frontend

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.

%I A365271 #75 Jul 27 2024 12:17:58
%S A365271 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 A365271 120,130,140,150,158,168,180,192,204,215,226,238,252,264,277,289,306,
%U A365271 320,336,351
%N 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.
%C A365271 Developed from the Destroying Democracy Puzzle created by Gordon Hamilton.
%C A365271 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 A365271 Gordon Hamilton, <a href="https://mathpickle.com/project/democracy/">Destroying Democracy!</a>, MathPickle, 2020.
%H A365271 Andrew Parkinson and Rob Pratt, <a href="/A365271/a365271_2.txt">Additional and conjectured terms to a(61)</a>.
%F A365271 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 A365271 For n=4, a(4)=6:
%e A365271 .
%e A365271               +-----------+---+
%e A365271   Region A -->| X   X   O | O |
%e A365271               +-----------+   |
%e A365271   Region B -->| X   X   O | O |
%e A365271               +-----------+   |<-- Region E
%e A365271   Region C -->| X   X   O | O |
%e A365271               +-----------+   |
%e A365271   Region D -->| O   O   O | O |
%e A365271               +-----------+---+
%e A365271 .
%e A365271 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 A365271 See the Hamilton link for more examples.
%Y A365271 Cf. A341319, A172477.
%K A365271 nonn,more,hard
%O A365271 1,2
%A A365271 _Andrew Parkinson_, Aug 30 2023
%E A365271 a(29)-a(44) obtained via integer linear programming by _Rob Pratt_, Jul 26 2024