login
Minimum number of dominoes on an n X n chessboard needed to prevent placement of another domino.
1

%I #65 Apr 03 2022 22:52:09

%S 0,2,3,6,9,12,17,22,27,34,41,48,57,66,75,86,97,108,122,134,147,163,

%T 178,192,210,227,243,263,282,300,322,343,363

%N Minimum number of dominoes on an n X n chessboard needed to prevent placement of another domino.

%C Each domino must cover exactly two adjacent squares of a row or column. Sequence inspired by question for 8 X 8 case in "Minimum Guard Problem" link.

%H Andrejs Cibulis and Walter Trump, <a href="https://doi.org/10.22364/bjmc.2020.8.4.02">Domino Exclusion Problem</a>, Baltic J. Modern Computing, Vol. 8 (2020), No. 4, 496-519.

%H A. Gyárfás, J. Lehel, and Zs. Tuza, <a href="https://doi.org/10.1016/0012-365X(88)90028-3">Clumsy packing of dominoes</a>, Discrete Mathematics, Volume 71, Issue 1 (1988), 33-46.

%H Peter Kagey, <a href="https://math.stackexchange.com/q/3191721/121988">Minimum number of dominoes on an n X n chessboard to prevent placement of another domino.</a>

%H Mathematics Stack Exchange user "Manin", <a href="https://math.stackexchange.com/questions/1573902/minimum-guard-problem">Minimum Guard Problem</a>.

%H Walter Trump, <a href="/A280984/a280984.pdf">Minimum Domino Packing</a>

%F Proved: a(n) >= A008810(n) for n>1; when n = 0 (mod 3), a(n) = A008810(n). - _Andrey Zabolotskiy_, Oct 22 2017

%F a(n) > n^2/3 + n/111 for large n not congruent to 0 (mod 3) [from Gyárfás, Lehel, Tuza]. - _Peter Kagey_, May 22 2019

%Y Cf. A008810 (maximum number of L-shaped trominoes with the same orientation in an n X n square).

%K nonn,more

%O 1,2

%A _Rick L. Shepherd_, Jan 11 2017, Aug 06 2017

%E a(10)-a(14) from _Lars Blomberg_, Aug 08 2017

%E a(15) from _Andrey Zabolotskiy_, Oct 20 2017

%E a(16)-a(17) from _Rob Pratt_ (see the link to _Peter Kagey_'s question) and a(18) added by _Andrey Zabolotskiy_, Feb 13 2020

%E a(19)-a(33) from _Walter Trump_, Jun 14 2020