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!)
A306954 Triangle read by rows: T(n, k), for 1 <= k <= n, is the maximum integer q such that k non-attacking armies of q queens can be placed on an n X n chessboard. 0
1, 4, 0, 9, 1, 0, 16, 2, 1, 1, 25, 4, 1, 1, 1, 36, 5, 2, 1, 1, 1, 49, 7 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

One has T(n, k) = 0 exactly when (n, k) = (2, 2) or (3, 3).

One has T(n, n) = 1 except when n = 2 or 3 (that is, when A000170(n) = 0).

For a fixed k, the sequence T(-, k) is nondecreasing.

For a fixed n, the sequence T(n, -) is nonincreasing.

For a fixed nonzero p, the sequence (T(k + p, k))_k is nonincreasing.  Indeed, given a configuration with k+1 armies on a k+p+1 chessboard, remove the row and column containing a given queen; this row and column can contain only queens of one army, so this yields a configuration of k armies on a k+p chessboard.

One has T(n, 1) = n^2 and T(n, 2) = A250000(n).

For a fixed k, one has, asymptotically in n, that 1/2.(n/k)^2 <= T(n, k) <= (n/k)^2, which can be proved as follows.

For the upper bound, let R(n, k) be defined as T(n, k) with rooks instead of queens.  Then, T(n, k) <= R(n, k) ~ (n/k)^2. Indeed, for 1 <= i <= k, say the i^th army controls a_i rows and b_i columns. The sum of the a_i's, as well as the sum of the b_i's, is at most n.  The size of the i^th army is at most a_i b_i. Therefore, one wants to maximize min(a_i b_i, i = 1..k). Ignoring rounding, the maximum is reached when all the a_i's and b_i's are equal.

For the lower bound, consider the n X n chessboard as a k X k grid with cells of size (n/k) X (n/k). Consider a configuration of k non-attacking queens on the k X k chessboard as in A000170(k). Place each of the k armies inside one cell occupied in that configuration. The precise placement is as follows: the army occupies the square whose vertices are the midpoints of the sides of the cell, hence has size 1/2.(n/k)^2. These armies are non-attacking.

LINKS

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

Arthur O'Dwyer, Peaceful Encampments, round 2 (blog post) for the "continuous case", that is, n = +oo.

EXAMPLE

Triangle begins:

   1

   4  0

   9  1  0

  16  2  1  1

  25  4  1  1  1

  36  5  2  1  1  1

  49  7  .  .  1  1  1

  64  9  .  .  .  1  1  1

  81 12  .  .  .  .  1  1  1

CROSSREFS

Column 1 gives A000290, n >= 1.

Cf. A000170 (non-attacking queens).

Column 2 gives A250000 (case of two armies).

Sequence in context: A291716 A022899 A081148 * A187606 A138478 A213472

Adjacent sequences:  A306951 A306952 A306953 * A306955 A306956 A306957

KEYWORD

nonn,tabl,more

AUTHOR

Benoit Jubin, Mar 17 2019

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 September 26 23:47 EDT 2020. Contains 337378 sequences. (Running on oeis4.)