A279408 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

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