A381749 Triangle read by rows: T(n,k), n >= k, is the maximum number of kings on a n X k chessboard so that no king attacks more than one other king.

1, 2, 2, 2, 4, 4, 3, 4, 6, 8, 4, 6, 8, 10, 12, 4, 6, 8, 11, 14, 16, 5, 8, 10, 13, 16, 18, 21, 6, 8, 12, 14, 18, 20, 24, 26, 6, 10, 12, 16, 20, 22, 26, 30, 33, 7, 10, 14, 18, 22, 25, 29, 32, 36, 40, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 8, 12, 16, 21, 26

Offset: 1

Author

Yifan Xie, Mar 06 2025

Keywords

• nonn
• tabl
• easy

Comments

Two kings attack each other if their corresponding cells have a common point.

Define a graph G = (V,E), where V is the set of kings and E includes all pairs of attacking kings. Then the constraint is equivalent to all connected components of G having 1 or 2 kings. Denote the connected components of G by blocks.

Extend the board P to P' by adding a row at the bottom and a column at the right. Define the neighborhood of a block B as the union of the 2 X 2 squares whose upper-left corner is a cell in B.

The neighborhoods of permitted blocks are shown, with B marked by 'X' and the remaining part of B's neighborhood by '-':

X- XX- X- X-- X-

--; ---; X- -X- X--

--; ---; -- .

Suppose that a cell C is in the neighborhoods of two distinct blocks B1 and B2. Then B1 and B2 both have a cell in the 2 X 2 square whose lower-right corner is C, but these two cells must be neighbor to each other, a contradiction.

Therefore, the neighborhoods of all blocks in P are non-overlapping in P'. Note that the size of a block's neighborhood is at least three times the size of the block. That is, T(n,k) <= (n+1)*(k+1)/3.

Also, note that 2 X 6 and 3 X 6 boards can be tiled with 6-sized neighborhoods, so m X 6 boards, where m > 1, can also be tiled with 6-sized neighborhoods. Therefore, the remaining details are not tedious to work with since a n X k board can generally be reduced to a (n mod 6) X (k mod 6) board.

Examples

			The triangle begins:
  n\k [1] [2]  [3]  [4]  [5]  [6]  [7]
  [1]  1;
  [2]  2,  2;
  [3]  2,  4,   4;
  [4]  3,  4,   6,   8;
  [5]  4,  6,   8,  10,  12;
  [6]  4,  6,   8,  11,  14,  16;
  [7]  5,  8,  10,  13,  16,  18,  21;
  ...
T(9,9) = 33:
  XX-XX-X-X
  ------X-X
  XX-XX----
  ------X-X
  X-X-X-X-X
  X-X------
  ----XX-XX
  X-X------
  X-X-XX-XX
		

Links

• Yifan Xie, Rows n = 1..100 of triangle, flattened

Crossrefs

A260090 gives the main diagonal.

Programs

PARI

T(n,k) = floor((n+1)*(k+1)/3) - if((n+1)*(k+1) % 6 == 3, 1, 0) - if(k == 3 && n % 3 == 0, 1, 0) - if(k == 6 && n % 6 == 3, 1, 0);

Formula

T(3*m,3) = 4*m;

T(6*m+3,6) = 14*m+8;

For k != 3 or 6, T(n,k) = floor((n+1)*(k+1)/3) - [(n+1)*(k+1) (mod 6) == 3] where [] denotes the Iverson bracket.