login
A308162
Area of the largest unpainted rectangle that is guaranteed to exist in every n X n grid with n painted cells.
0
0, 1, 2, 3, 4, 6, 6, 8, 9, 10, 12, 12, 15, 16, 18, 18, 20
OFFSET
1,3
COMMENTS
It seems that in the optimal solutions, the largest rectangle always occurs in one of the corners of the grid.
LINKS
dxdy forum, post (in Russian).
EXAMPLE
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.
. . . . . . #
. . # . . . .
. . . . # . .
. # . . . . .
. . . . . # .
. . . # . . .
# . . . . . .
CROSSREFS
Sequence in context: A278400 A239492 A034298 * A092404 A094871 A157450
KEYWORD
nonn,hard,more
AUTHOR
Dmitry Kamenetsky, May 15 2019
STATUS
approved