Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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