Notes on A274650 and Proof by Non-Attacking Queens.

N. J. A. Sloane
(njasloane@gmail.com)
June 06 2017

Theorem 1: Every column and every diagonal of the triangle in
A274650 is a permutation of the non-negative integers.

We begin with three lemmas. Lemmas 3 and 4 are needed for the proof,
Lemma 2 is included for completeness.

Lemma 2: The maximal number of pairwise mutually
non-attacking queens that can be placed on an n X n chess-board is
n if n = 1 or n > 3, and is n-1 if n = 2 or 3.

This is well-known: see references in A000170.

Lemma 3: The maximal number of pairwise mutually
non-attacking queens that can be placed on a "half-board",
that is, on a right triangular chess-board with n cells on each side,
is the nearest integer to 2n/3 except when n=4, when the answer is 2 rather than 3.

For proof, see:
Paul Vanderlind, Richard K. Guy, and Loren C. Larson, The Inquisitive Problem Solver, 
MAA, 2002; Problem 252, pages 67, 87, 198 and 276.
See A274616 for illustrations.

Lemma 4: The maximal number of pairwise mutually non-attacking queens 
that can be placed on a "quarter-board", that is, on a a symmetric
pyramid-shaped chess-board with rows of squares of lengths n, n-2, n-4, ..., 
ending with either 2 or 1 squares, is at most floor(n/2) for n >= 2, or 1 if n=1.
Proof: There can be at most one queen per row. QED

The first 100 values are known exactly (see A287864, which also has illustrations),
but beyond that the exact values are not known.
 
Theorem 5: Every column of the triangle in
A274650 is a permutation of the non-negative integers.

Proof: Let T(n,k) (0 <= k <= n) denote the entry in position (n,k)
of the triangle, so that the columns are numbered 0, 1, 2, ... 
Suppose column c is not a permutation, and let k be the smallest 
missing number in that column.  Choose n_0 so that T(n,c) > k for
all n >= n_0.

For n >= n_0, T(n,c) would be k unless there were an entry k
which blocks it, either to the West of cell (n,c), to the North-West,
to the North, or to the North-East. Replace all those entries k by queens.
By definition, these are mutually non-attacking queens.

There are most c queens in columns 0,1,2,...,c-1, whose influence on
the cells in column c does not extend below cell(n_1,c), say.

Choose n to be much greater than n_2 := max(n_0, n_1). Each of the n-n_2+1 cells in column
c in the range (n_2,c) through (n,c) must see a queen to the North or North-East.
These queens all lie in the "quarter-board" bounded by column c, the top diagonal 
line of cells (i,i), and the antidiagonal line through (n,c), so their number
is at most (n-c)/2, by Lemma 4.  But for n large, n-n_2+1 > (n-c)/2, so
there are not enough queens in the quarter-board to cover all the 
cells in column c. QED

Theorem 6: Every diagonal of the triangle in
A274650 is a permutation of the non-negative integers.

The proof is similar to that of Theorem 5, but using Lemma 3 instead of Lemma 4.
We consider diagonal d (d>=0). Suppose k is the smallest number
that is missing from that diagonal. Replace the k's in the triangle
by queens.  The d or fewer queens in diagonals 0 though d-1 have only a 
limited influence on the cells of diagonal d. So beyond a certain point,
every cell on the diagonal must see a queen to the West. But these
queens all lie in a half-board bounded by the left edge, the diagonal itself,
and the row through the diagonal cell we are considering. By Lemma 3, 
this number is of order 2n/3, while there are order n cells that must be covered.  QED

Theorems 5 and 6 imply Theorem 1.