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

Author

Andrey Zabolotskiy, Dec 16 2016

Keywords

• nonn
• tabl
• easy

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).

Examples

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

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.

Crossrefs

Cf. A075561, A279402, A279407, A279209.

Programs

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 *)

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

Formula

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