A279408 - OEIS

%I #21 Mar 09 2017 10:01:09

%S 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,

%T 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,

%U 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

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

%C 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.

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

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

%H Indranil Ghosh, <a href="/A279408/b279408.txt">Rows 1..100, flattened</a>

%H Dan Freeman, <a href="http://www.slideshare.net/DanFreeman1/chessboard-puzzles-part-4-other-surfaces-and-variations-42702023">Chessboard Puzzles Part 4 - Other Surfaces and Variations</a>.

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

%e T(7,7)=7 can be reached by:

%e ...K...

%e ......K

%e ..K....

%e .....K.

%e .K.....

%e ....K..

%e K......

%t Flatten[Table[Ceiling[Max[m Ceiling[n/3], n Ceiling[m/3]]/3],{n, 1, 13}, {m, 1, n}]] (* _Indranil Ghosh_, Mar 09 2017 *)

%o (PARI) T(n,m) = ceil(max(m*ceil(n/3), n*ceil(m/3))/3)

%o for(n=1,20,for(m=1,n, print1(T(n,m)", "))) \\ _Charles R Greathouse IV_, Dec 16 2016

%Y Cf. A075561, A279402, A279407, A279209.

%K nonn,tabl,easy

%O 1,7

%A _Andrey Zabolotskiy_, Dec 16 2016