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

Author

Yifan Xie, Mar 12 2025

Keywords

• nonn
• tabl
• easy

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

Examples

			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
		

Links

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

Crossrefs

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

Programs

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))));

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).