login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A260090 Maximum number of kings on an n X n chessboard such that no king attacks more than one other king. 2
1, 2, 4, 8, 12, 16, 21, 26, 33, 40, 48, 56, 65, 74, 85 (list; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=1..15.

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

A103139(n) and A181018(n) are upper bounds.

A260113 is the corresponding sequence for queens.

Cf. A103469.

Sequence in context: A256409 A256403 A308013 * A256941 A324174 A047836

Adjacent sequences:  A260087 A260088 A260089 * A260091 A260092 A260093

KEYWORD

nonn,more

AUTHOR

Rob Pratt, Jul 15 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 30 05:35 EDT 2020. Contains 334712 sequences. (Running on oeis4.)