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
Examples
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
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.
Formula
T(n,k) = T(k,n).
T(2,k) = k + 2.
T(n,2) = n + 2.