login
Area of the largest unpainted rectangle that is guaranteed to exist in every n X n grid with n painted cells.
0

%I #17 Jul 16 2019 11:49:28

%S 0,1,2,3,4,6,6,8,9,10,12,12,15,16,18,18,20

%N Area of the largest unpainted rectangle that is guaranteed to exist in every n X n grid with n painted cells.

%C It seems that in the optimal solutions, the largest rectangle always occurs in one of the corners of the grid.

%H dxdy forum, <a href="https://dxdy.ru/post1393342.html">post</a> (in Russian).

%e The following 7 X 7 grid contains 7 painted cells (#). Its largest unpainted rectangle has area 6 (1 X 6 or 2 X 3) and no other such grid has the largest unpainted rectangle with area 5. Hence a(7) = 6.

%e . . . . . . #

%e . . # . . . .

%e . . . . # . .

%e . # . . . . .

%e . . . . . # .

%e . . . # . . .

%e # . . . . . .

%K nonn,hard,more

%O 1,3

%A _Dmitry Kamenetsky_, May 15 2019