A379726 Minimum number of kings that must be placed on an n X n chessboard such that each square is attacked or occupied by at least two kings.
2, 3, 8, 8, 10, 18, 18, 21, 32, 32, 36, 50, 50, 55, 72, 72, 78, 98, 98, 105, 128, 128, 136, 162, 162, 171, 200, 200, 210, 242, 242, 253, 288, 288, 300, 338, 338, 351, 392, 392, 406, 450, 450, 465, 512, 512, 528, 578, 578, 595, 648, 648, 666, 722, 722, 741, 800, 800, 820, 882, 882, 903, 968, 968, 990, 1058, 1058, 1081, 1152, 1152, 1176, 1250, 1250, 1275, 1352, 1352, 1378, 1458, 1458, 1485, 1568, 1568, 1596, 1682, 1682, 1711, 1800, 1800, 1830, 1922, 1922, 1953, 2048, 2048, 2080, 2178, 2178, 2211, 2312
Offset: 2
Keywords
Examples
For a 3 by 3 chessboard, the three kings could be placed like this (where o is an empty square and k is a king): ooo kkk ooo For a 4 by 4 chessboard, the kings could be placed like this: oooo kkkk okko okko
Links
- Rob Pratt, Table of n, a(n) for n = 2..100
- Colin Beveridge, Proof of the case where n is a multiple of 3
- Matthew Scroggs, December 23
- Matthew Scroggs, Friendly squares
- Matthew Scroggs, Python code to compute A379726
- Puzzling StackExchange, Minimum Number of Squares to Color
- Dominic McCarty, Illustration of a(n) for n = 2..100
Formula
If n is not a multiple of 3, a(n) = 2*floor((n+2)/3)^2.
If n is a multiple of 3, it is conjectured that a(n)=2*(n/3)^2+n/3.
The above conjectures are true (see Beveridge link). - Colin Beveridge, Jan 13 2025
Extensions
a(15)-a(100) via integer linear programming by Rob Pratt, Jan 02 2025
Comments