A376167 Square array read by antidiagonals: T(n,k) = smallest r such that every n X k binary matrix with r ones contains a 2 X 2 submatrix of ones, with n, k >= 2.

4, 5, 5, 6, 7, 6, 7, 8, 8, 7, 8, 9, 10, 9, 8, 9, 10, 11, 11, 10, 9, 10, 11, 13, 13, 13, 11, 10, 11, 12, 14, 15, 15, 14, 12, 11, 12, 13, 15, 16, 17, 16, 15, 13, 12, 13, 14, 16, 18, 19, 19, 18, 16, 14, 13, 14, 15, 17, 19, 20, 22, 20, 19, 17, 15, 14, 15, 16, 18, 21, 22, 23, 23, 22, 21, 18, 16, 15

Offset

2,1

References

Donald E. Knuth, The Art of Computer Programming, Vol. 4B: Combinatorial Algorithms, Part 2, Addison-Wesley, 2023, section 7.2.2.2, pp. 289-291.

Links

Table of n, a(n) for n=2..79.

Formula

T(n,k) = T(k,n).

T(2,k) = k + 2.

T(n,2) = n + 2.

Example

Array begins (cf. Table 5 in Knuth (2023), section 7.2.2.2, p. 291, where T(n,k) is denoted by Z(m,n)):
  n\k|   2   3   4   5   6   7   8   9  10  11  12  ...
  -----------------------------------------------------
   2 |   4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, ...
   3 |   5,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, ...
   4 |   6,  8, 10, 11, 13, 14, 15, 16, 17, 18, 19, ...
   5 |   7,  9, 11, 13, 15, 16, 18, 19, 21, 22, 23, ...
   6 |   8, 10, 13, 15, 17, 19, 20, 22, 23, 25, 26, ...
   7 |   9, 11, 14, 16, 19, 22, 23, 25, 26, 28, 29, ...
   8 |  10, 12, 15, 18, 20, 23, 25, 27, 29, 31, 33, ...
   9 |  11, 13, 16, 19, 22, 25, 27, 30, 32, 34, 37, ...
  10 |  12, 14, 17, 21, 23, 26, 29, 32, 35, 37, 40, ...
  11 |  13, 15, 18, 22, 25, 28, 31, 34, 37, 40, 43, ...
  12 |  14, 16, 19, 23, 26, 29, 33, 37, 40, 43, 46, ...
  ...
T(3,4) = 8 because, no matter how 8 ones are arranged in a 3 X 4 matrix, a 2 X 2 submatrix of ones cannot be avoided (in the left configuration below, for example, the submatrix elements are highlighted by parentheses). 7 ones can avoid such submatrix (right).
.
  (1) 0 (1) 1       1  0  1  1
   0  1  0  1       0  1  0  1
  (1) 1 (1) 0       1  1  0  0

Crossrefs

Cf. A001197 (main diagonal), A347472, A350296.

Sequence in context: A248926 A107575 A350361 * A205677 A178400 A114458

Adjacent sequences: A376164 A376165 A376166 * A376168 A376169 A376170

Keyword

nonn,tabl

Author

Paolo Xausa, Sep 13 2024

Status

approved