A379636 Triangle read by rows: T(n,k) (n >= k) is the maximum number of black cells in a n X k grid such that no black cell is edge-adjacent to more than one black cell.

1, 2, 2, 2, 4, 5, 3, 4, 7, 8, 4, 6, 9, 11, 14, 4, 6, 10, 12, 16, 18, 5, 8, 12, 15, 19, 22, 26, 6, 8, 14, 16, 22, 24, 30, 32, 6, 10, 15, 19, 24, 28, 33, 38, 42, 7, 10, 17, 20, 27, 30, 37, 40, 47, 50, 8, 12, 19, 23, 30, 34, 41, 46, 52, 57, 63, 8, 12, 20, 24, 32

Offset

1,2

Comments

Two cells are edge-adjacent if they have a common edge.

T(n,1) and the upper bound are shown by blackening the left two cells in each three consecutive cells (refer to T(8,1) example).

If both n and k are even, T(n,k) is reached by checkerboard coloring. The upper bound follows from T(2,2) = 2.

Suppose that k is odd. T(n,k) can be constructed by applying the T(n,1) construction on each odd-numbered row, and the coloring of even-numbered rows opposite to odd-numbered ones (refer to T(7,7) example). If n is even, the upper bound follows from T(n,k) <= T(n,k-1) + T(n,1).

If n is odd, we choose an up-and-right path visiting cells a_1, a_2, ..., a_(n+k-1) in that order. Set a_1 as the lower-left corner and a_(n+k-1) as the upper-right corner. The edge a_(2i) - a_(2i+1) continues the previous direction. If a_(2i+1) is not on the upper edge or on the right edge, choose a_(2i+2) such that a_(2i+1) and a_(2i+2) are not both black; Suppose the contrary, and then a_(2i+1) and its upper and right neighbors are all black, a contradiction.

Therefore we divide the grid into the upper-left and lower-right parts, each of which can be divided into 2 X 2 grids, so there are at most (n-1)*(k-1)/2 black cells. As for the path, the part not on the upper edge or on the right edge has no more than half black cells, while the edge part contains at most n cells, hence T(n,k) <= (n-1)*(k-1)/2 + (k-1)/2 + T(n,1) = n*(k-1)/2 + ceiling(2*n/3).

The following example illustrates the colored grid and the corresponding path:

XX_XX_XX_ ......XX_

__X__X__X ......_..

_X_XX_XX_ ....X_X..

X_X__X__X ...._....

X_X_X_XX_ X_X_X....

___X_X__X _........

XX_X_X_X_ X........

Links

Yifan Xie, Rows 1..100 of triangle, flattened

Formula

If n and k are both even, T(n,k) = n*k/2;

If n is even and k is odd, T(n,k) = n*(k-1)/2 + ceiling(2*n/3);

If n is odd and k is even, T(n,k) = k*(n-1)/2 + ceil(2*k/3);

If n and k are both odd, T(n,k) = n*(k-1)/2 + ceiling(2*n/3).

Example

The triangle begins:
  n\k [1] [2]  [3]  [4]  [5]  [6]  [7]
  [1]  1;
  [2]  2,  2;
  [3]  2,  4,   5;
  [4]  3,  4,   7,   8;
  [5]  4,  6,   9,  11,  14;
  [6]  4,  6,  10,  12,  16,  18;
  [7]  5,  8,  12,  15,  19,  22,  26;
  ...
T(8,1) = 6:
  XX_XX_XX
T(7,7) = 26:
  XX_X_XX
  __X_X__
  XX_X_XX
  --X_X__
  XX_X_XX
  __X_X__
  XX_X_XX

Prog

(PARI) T(n, k)=if(n%2==0 && k%2==0, n*k/2, if(n%2==0, n*(k-1)/2+ceil(2*n/3), if(k%2==0, k*(n-1)/2+ceil(2*k/3), n*(k-1)/2+ceil(2*n/3))));

Crossrefs

Cf. A260090 (where adjacency is defined by having a common vertex)

Sequence in context: A299204 A230141 A151680 * A381030 A231351 A024681

Adjacent sequences: A379633 A379634 A379635 * A379637 A379638 A379639

Keyword

nonn,tabl,easy

Author

Yifan Xie, Mar 12 2025

Status

approved