A279408 Triangle read by rows: T(n,m) (n>=m>=1) = domination number for kings' graph on an n X m toroidal board.

1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 2, 2, 2, 4, 4, 2, 2, 2, 4, 4, 4, 3, 3, 3, 5, 5, 6, 7, 3, 3, 3, 6, 6, 6, 8, 8, 3, 3, 3, 6, 6, 6, 9, 9, 9, 4, 4, 4, 7, 7, 8, 10, 11, 12, 14, 4, 4, 4, 8, 8, 8, 11, 11, 12, 15, 15, 4, 4, 4, 8, 8, 8, 12, 12, 12, 16, 16, 16, 5, 5, 5, 9, 9, 10, 13, 14, 15, 18, 19, 20, 22

Offset

1,7

Comments

That is, the minimal number of kings needed to cover an n X m toroidal chessboard so that every square has a king on it, is under attack by a king, or both.

For the usual non-toroidal case, the formula is ceiling(m/3)*ceiling(n/3).

References

John J. Watkins, Across the Board: The Mathematics of Chessboard Problem, Princeton University Press, 2004, pages 144-149.

Links

Indranil Ghosh, Rows 1..100, flattened

Dan Freeman, Chessboard Puzzles Part 4 - Other Surfaces and Variations.

Formula

T(n,m) = ceiling(max(m*ceiling(n/3), n*ceiling(m/3))/3).

Example

T(7,7)=7 can be reached by:
...K...
......K
..K....
.....K.
.K.....
....K..
K......

Mathematica

Flatten[Table[Ceiling[Max[m Ceiling[n/3], n Ceiling[m/3]]/3], {n, 1, 13}, {m, 1, n}]] (* Indranil Ghosh, Mar 09 2017 *)

Prog

(PARI) T(n, m) = ceil(max(m*ceil(n/3), n*ceil(m/3))/3)
for(n=1, 20, for(m=1, n, print1(T(n, m)", "))) \\ Charles R Greathouse IV, Dec 16 2016

Crossrefs

Cf. A075561, A279402, A279407, A279209.

Sequence in context: A325273 A352541 A359438 * A135592 A022912 A318955

Adjacent sequences: A279405 A279406 A279407 * A279409 A279410 A279411

Keyword

nonn,tabl,easy

Author

Andrey Zabolotskiy, Dec 16 2016

Status

approved