cp's OEIS Frontend

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.

%I A381749 #21 Mar 22 2025 17:16:27
%S A381749 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,
%T A381749 8,12,14,18,20,24,26,6,10,12,16,20,22,26,30,33,7,10,14,18,22,25,29,32,
%U A381749 36,40,8,12,16,20,24,28,32,36,40,44,48,8,12,16,21,26
%N 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.
%C A381749 Two kings attack each other if their corresponding cells have a common point.
%C A381749 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.
%C A381749 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.
%C A381749 The neighborhoods of permitted blocks are shown, with B marked by 'X' and the remaining part of B's neighborhood by '-':
%C A381749  X-  XX-  X-  X--   X-
%C A381749  --; ---; X-  -X-  X--
%C A381749           --; ---; -- .
%C A381749 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.
%C A381749 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.
%C A381749 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.
%H A381749 Yifan Xie, <a href="/A381749/b381749.txt">Rows n = 1..100 of triangle, flattened</a>
%F A381749 T(3*m,3) = 4*m;
%F A381749 T(6*m+3,6) = 14*m+8;
%F A381749 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.
%e A381749 The triangle begins:
%e A381749   n\k [1] [2]  [3]  [4]  [5]  [6]  [7]
%e A381749   [1]  1;
%e A381749   [2]  2,  2;
%e A381749   [3]  2,  4,   4;
%e A381749   [4]  3,  4,   6,   8;
%e A381749   [5]  4,  6,   8,  10,  12;
%e A381749   [6]  4,  6,   8,  11,  14,  16;
%e A381749   [7]  5,  8,  10,  13,  16,  18,  21;
%e A381749   ...
%e A381749 T(9,9) = 33:
%e A381749   XX-XX-X-X
%e A381749   ------X-X
%e A381749   XX-XX----
%e A381749   ------X-X
%e A381749   X-X-X-X-X
%e A381749   X-X------
%e A381749   ----XX-XX
%e A381749   X-X------
%e A381749   X-X-XX-XX
%o A381749 (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);
%Y A381749 A260090 gives the main diagonal.
%K A381749 nonn,tabl,easy
%O A381749 1,2
%A A381749 _Yifan Xie_, Mar 06 2025