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

%I #9 Sep 14 2024 06:47:00

%S 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,

%T 11,12,14,15,15,14,12,11,12,13,15,16,17,16,15,13,12,13,14,16,18,19,19,

%U 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

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

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

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

%F T(2,k) = k + 2.

%F T(n,2) = n + 2.

%e 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)):

%e n\k| 2 3 4 5 6 7 8 9 10 11 12 ...

%e -----------------------------------------------------

%e 2 | 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...

%e 3 | 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...

%e 4 | 6, 8, 10, 11, 13, 14, 15, 16, 17, 18, 19, ...

%e 5 | 7, 9, 11, 13, 15, 16, 18, 19, 21, 22, 23, ...

%e 6 | 8, 10, 13, 15, 17, 19, 20, 22, 23, 25, 26, ...

%e 7 | 9, 11, 14, 16, 19, 22, 23, 25, 26, 28, 29, ...

%e 8 | 10, 12, 15, 18, 20, 23, 25, 27, 29, 31, 33, ...

%e 9 | 11, 13, 16, 19, 22, 25, 27, 30, 32, 34, 37, ...

%e 10 | 12, 14, 17, 21, 23, 26, 29, 32, 35, 37, 40, ...

%e 11 | 13, 15, 18, 22, 25, 28, 31, 34, 37, 40, 43, ...

%e 12 | 14, 16, 19, 23, 26, 29, 33, 37, 40, 43, 46, ...

%e ...

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

%e .

%e (1) 0 (1) 1 1 0 1 1

%e 0 1 0 1 0 1 0 1

%e (1) 1 (1) 0 1 1 0 0

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

%K nonn,tabl

%O 2,1

%A _Paolo Xausa_, Sep 13 2024