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

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

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

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

Adjacent sequences: A308159 A308160 A308161 * A308163 A308164 A308165

Keyword

nonn,hard,more

Author

Dmitry Kamenetsky, May 15 2019

Status

approved