[seqfan] Re: A269526, an infinite Sudoku-type array

Neil Sloane njasloane at gmail.com
Fri Jul 1 15:18:12 CEST 2016


I agree that argument proves that the columns are permutations.

The proof isn't quite so clear for the rows. Take row 1. Suppose j is
missing. Then
every antidiagonal must contain a j (before it reaches the first row). But
the antidiagonals
are getting longer and longer.

What we have to is show (roughly) that if we take a triangle
formed by the first K antidiagonals, containing about K(K+1)/2
grid points, then we cannot place K nonattacking queens on this board
(thinking of the positions
of the j's as queens)

Now we can place K nonattacking queens on a square k X K board (see
A000170). But we surely cannot
do it on a triangular board.  Proof?

Our problem is not exactly that, since we stop the antidiagonals just
before they reach the top row.

But still, it is a nice question: Take a triangular chess board containing
K*(K+1)/2 cells.
What is the max number of nonattacking queens? This must be a known
sequence?
Maybe it begins 1,1,2,2,3?  Is there a proof that it is <= (K+1)/2 ?

Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com


On Fri, Jul 1, 2016 at 7:34 AM, Bob Selcoe <rselcoe at entouchonline.net>
wrote:

> Hi,
>
> Unless I'm missing something, I think there's a straightforward proof that
> the columns, rows and diagonals are permutations.
>
> Let the array T(n,k) in A269526 start T(0,0).
>
> Let j be the smallest number not yet appearing in Column K, and let F be
> the first cell in K where j may appear.  j only must avoid elements from
> prior (i.e, to the left of K) columns.  Since no element can repeat in any
> columns, the maximum number of elements that j must avoid is 3k (i.e, the
> elements in the row and two diagonals to the left of where j is being
> evaluated).  Therefore j must appear no later than 3k+1 places after F, and
> columns are permutations.
>
> Same logic applies to the rows and diagonals, though the maximum number of
> places after F is different: 2n+k+1 for rows and n+2k+1 for diagonals.  The
> constraints probably can be tightened, but it's not necessary for a proof.
>
> If this proof is acceptable I would like to add it as a comment in A269526.
>
> Cheers,
> Bob S.
>
> --------------------------------------------------
> From: "Neil Sloane" <njasloane at gmail.com>
> Sent: Wednesday, June 29, 2016 1:24 PM
> To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
> Subject: [seqfan] A269526, an infinite Sudoku-type array
>
> Dear Seq Fans,  The following is a pretty interesting recent sequence:
>>
>> Array read by anti-diagonals upwards in which each term is the least
>> positive value satisfying the condition that no row, column, or diagonal
>> contains a repeated term.
>>
>> The sequence is A269526.  I just added the first three rows and the main
>> diagonal as A274315 ff. (They all need b-files.)
>>
>> The array begins:
>>
>> 1, 3, 2, 6, 4, 5, 10, 11, 13, 8, 14, 18, 7, 20, 19, ...
>> 2, 4, 5, 1, 8, 3, 6, 12, 14, 16, 7, 15, 17, 9, 22, ...
>> 3, 1, 6, 2, 9, 7, 5, 4, 15, 17, 12, 19, 18, 21, 8, ...
>> 4, 2, 3, 5, 1, 8, 9, 7, 16, 6, 18, 17, 11, 10, 23, ...
>> 5, 7, 1, 4, 2, 6, 3, 15, 9, 10, 13, 8, 20, 14, 12, ...
>> ...
>>
>> It seems very likely that every row, columns and diagonal (meaning
>> diagonals parallel to the main diagonal) is a perm of the natural numbers,
>> but I didn't try to find a proof.
>>
>> The first col is just 1,2,3,4,... but the next few columns could also be
>> added as new? entries.
>>
>> There are a lot of other related sequences, for example, in row n, where
>> does 1 appear?
>>
>> It is unusual to see such a nice array which is unrelated to any other
>> sequence in the OEIS!  (But I didn't try Superseeker).
>>
>> This looks like a lovely problem crying out to be analyzed.
>>
>> Best regards
>> Neil
>>
>> Neil J. A. Sloane, President, OEIS Foundation.
>> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
>> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
>> Phone: 732 828 6098; home page: http://NeilSloane.com
>> Email: njasloane at gmail.com
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>


More information about the SeqFan mailing list