OFFSET
1,2
COMMENTS
Suggested by a problem involving parking cars in Marx (2015). The Marx problem is slightly different, however, since a solution in her book shows one car that is adjacent to two of its eight neighbors.
Can be formulated as an integer linear programming problem as follows. Define a graph with a node for each cell and an edge for each pair of cells that are a king's move apart. Let binary variable x[i] = 1 if a king appears at node i, and 0 otherwise. The objective is to maximize sum x[i]. Let N[i] be the set of neighbors of node i. To enforce the rule that x[i] = 1 implies sum {j in N[i]} x[j] <= 1, impose the linear constraint sum {j in N[i]} x[j] - 1 <= (|N[i]| - 1) * (1 - x[i]) for each i. - Rob Pratt, Jul 16 2015
An alternative formulation uses constraints x[i] + x[j] + x[k] <= 2 for each forbidden triple of nodes.
REFERENCES
Dale Gerdemann et al., Discussions on Sequence Fans Mailing List, July 15 2015.
Patricia Marx, Let's Be Less Stupid, Hachette, 2015.
LINKS
Manfred Scheucher, Python Script
FORMULA
Conjecture: For n != 3, a(n) = n(n+2)/3 + [n mod 3 = 2]/3 - [n mod 6 = 2]
Equivalent conjecture for n >= 5: a(n) = a(n-1) + n - A103469(n-2). - Bob Selcoe, Jul 17 2015
EXAMPLE
a(8) = 26:
XX_XX_XX
________
XX_XX_XX
________
XX_XX_X_
_______X
X_X_X___
X_X_X_XX
a(15) = 85:
XX_XX_XX_XX_X_X
____________X_X
XX_X_X_X_XX____
___X_X_X____X_X
XX_______XX_X_X
___XX_XX_______
XX_______X_X_XX
___X_X_X_X_X___
XX_X_X_______XX
_______XX_XX___
X_X_XX_______XX
X_X____X_X_X___
____XX_X_X_X_XX
X_X____________
X_X_XX_XX_XX_XX
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Rob Pratt, Jul 15 2015
STATUS
approved