Benoit Jubin, Improved lower bound for A250000 ============================================== Posting to Sequence Fans Mailing List, Feb 24 2015 with comments from Ron Pratt and Bob Selcoe. (Partially edited by N. J. A. Sloane, Nov 18 2018.) ---------------------------------------------- Benoit Jubin, Feb 24 2015: 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> 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? ---------------------------------------------- Benoit Jubin, Feb 25 2015: Dear Bob 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. ----------------------------------------------