[seqfan] Re: Improved lower bound for A250000

[Benoît Jubin]

Dear Rob,

I think that you interpret the coordinates correctly. My configuration is
only a slight modification of yours, but not exactly the same, as you can
see in my example for n=24 (in a previous email of this conversation).
Also, the bound you give on the webpage, namely (after simplification),
a(4m) >= floor( (9/4)*m^2 + m/2 - 3/4 )
made me think that your configuration is given as follows (for n=4m):
One decomposes the chessboard into 16 smaller (m,m) chessboards as follows:
.A.B
.C.D
W.X.
Y.Z.
where the dots are empty chessboards and
A, B, C, D contain the queens of one color
and
W, X, Y, Z contain the queens of the other color.
Borrowing to the language of matrices, the occupied squares are as follows:
A: all squares,
B: strict lower-right half,
C: strict upper quarter, that is, intersection of the strict upper-left
half and the strict upper-right half,
D: upper-left half plus the first subdiagonal,
W: lower-right half,
X: intersection of the strict lower-right half minus the first subdiagonal
and the lower-left half,
Y: upper-left half,
Z: all squares minus the upper-left one.

What I meant by "equalizing the opposite boundaries" is this: in the picture

....|....|......../

....|....|......./.

....|....|....../..

....|.../....../...

....|../....../....

.....\/.......|....

..............|....

..............|.../

..............|../.

..--+.........+--..

./..|..............

/...|..............

....|..............

....|......./\.....

..../....../..|....

.../....../...|....

../......|....|....
./.......|....|....

/........|....|....

each of the lines x=1/4, x=1/2, x=3/4, y=1/2, y=x, y=x+1/3, y=x-1/3,y=1-x
borders a white region and a black region, and the length during which it
borders each is equal. This is how I optimized your solution: by
translating these lines, one adds to the army of one color while removing
from the other color (compensate this on the other pair of regions, to
still have equally sized armies), so one deduces that for the optimal
configuration of this sort, "opposite boundaries" must have same length.


I am mainly interested in asymptotics, where it does not matter whether n
is divisible by 4 or not. But for a given n, not necessarily divisible by
4, I would first draw these regions, and for any given square, if more than
half of it is within the region, I would put a queen. For the 50%-squares,
put queens for one out of the two regions. Finally (possibly not needed),
give or take a few queens on the boundaries to get an admissible
configuration.


Best,

Benoît





On Wed, Feb 25, 2015 at 6:35 AM, Bob Selcoe <rselcoe at entouchonline.net>
wrote:

> Hi Benoit,
>
> Excellent!  This certainly is an improvement.
>
> But I'm having a little difficulty following how you've obtained the upper
> and lower bounds, as well as your description of coordinates.
>
> So for my n=24 a(n)=83 board, wouldn't you also say the queens of one
> color are in the two regions x<1/4, y<1/2, x<y<x+1/3
> and 1/2<x<3/4, y<x-1/3, y<1-x, while the queens of the other color are
> obtained by central symmetry (or at least something approximating central
> symmetry)???
>
> So I don't see how the definitions between your and my configurations
> differ; that is, when you say:
>
>  I obtained these coefficients by equalizing the lengths of the "opposite"
>>> boundaries of the armies  (this already improves (by 1) on the "Board 4"
>>> example of the webpage).
>>>
>>
> I'm not sure what you "equalized" to gain the improvement.
>
> But still, there is definite improvement.
>
> I probably won't have time to look into a structural pattern for n = 4m
> for several days; my guess is one exists based on your approach, which will
> improve upon mine.  Will you have a chance to see if such a pattern exists?
>
> Best Wishes,
> Bob Selcoe
>
> --------------------------------------------------
> From: "Benoît Jubin" <benoit.jubin at gmail.com>
> Sent: Tuesday, February 24, 2015 11:25 AM
> To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
> Subject: [seqfan] Re: Improved lower bound for A250000
>
>
>  Dear Rob,
>> I improved by one the final board on the webpage by using the same idea as
>> for my asymptotic bound, but you are right that in this specific case, the
>> result is not centrally symmetric. From the last example on the webpage, I
>> made marginal changes along the diagonals (in the [0,1]^2 coordinates)
>> y=x+1/3 (deleted 3 Ws, added 5 Bs) and y=x-1/3 (deleted 4 Bs, added 4Ws):
>>
>> ------------------------
>>
>> ......WWWWWW............
>>
>> ......WWWWWW...........W
>>
>> ......WWWWWW..........WW
>>
>> ......WWWWWW.........WWW
>>
>> ......WWWWWW........WWWW
>>
>> ......WWWWW........WWWWW
>>
>> .......WWW........WWWWWW
>>
>> ........W.........WWWWWW
>>
>> ..................WWWWWW
>>
>> ..................WWWWW.
>>
>> ..................WWWW..
>>
>> ..................WWW...
>>
>> ....BB..................
>>
>> ...BBB..................
>>
>> ..BBBB..................
>>
>> .BBBBB..................
>>
>> BBBBBB..........B.......
>>
>> BBBBBB.........BBB......
>>
>> BBBBBB........BBBB......
>>
>> BBBBB........BBBBB......
>>
>> BBBB........BBBBBB......
>>
>> BBB.........BBBBBB......
>>
>> BB..........BBBBBB......
>>
>> B...........BBBBBB......
>>
>> ------------------------
>>
>>
>>
>> On Tue, Feb 24, 2015 at 6:13 PM, Rob Pratt <Rob.Pratt at sas.com> wrote:
>>
>>  Please share your n =24 solution.  Under the central symmetry constraint,
>>> I get a maximum of 80, not 84.
>>>
>>> -----Original Message-----
>>> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Benoît
>>> Jubin
>>> Sent: Tuesday, February 24, 2015 11:50 AM
>>> To: Sequence Fanatics Discussion list
>>> Subject: [seqfan] Improved lower bound for A250000
>>>
>>> Dear seqfans,
>>>
>>> Let a(n)=A250000(n) be the maximum size of coexisting armies of queens on
>>> an (n,n) chessboard.
>>>
>>> By modifying the Pratt--Selcoe configuration, I improved the best known
>>> lower bound from
>>> a(n) > (9/4)*(n/4)^2
>>> to
>>> a(n) > (7/3)*(n/4)^2.
>>> I have been sloppy with side effects, but to be on the safe side, let's
>>> say
>>> a(n) > (7/3)*(floor(n/4))^2 - (3+8*sqrt(2)/3)*ceiling(n/4), where the
>>> coefficient 3+8*sqrt(2)/3 is a perimeter that you can compute from the
>>> following description.
>>>
>>> The configuration in the limit n = infinity is as follows: denoting by
>>> x,y
>>> in [0,1] the coordinates on the chessboard, the queens of one color are
>>> in
>>> the two regions x<1/4, y<1/2, x<y<x+1/3 and 1/2<x<3/4, y<x-1/3, y<1-x and
>>> the queens of the other color are obtained by central symmetry. As you
>>> can
>>> guess, I obtained these coefficients by equalizing the lengths of the
>>> "opposite" boundaries of the armies (this already improves (by 1) on the
>>> "Board 4" example of the webpage).
>>>
>>> Using an easy upper bound, one has asymptotically
>>> (2+1/3)*(n/4)^2 < a(n) < 4*(n/4)^2.
>>> Anyone to help fill the gap?
>>>
>>> Best,
>>> Benoit
>>>
>>> _______________________________________________
>>>
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>> _______________________________________________
>>>
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>