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<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. Would anyone like to help fill the gap? ---------------------------------------------- Rob Pratt, Feb 24 2015: Please share your n =24 solution. Under the central symmetry constraint, I get a maximum of 80, not 84. ---------------------------------------------- Benoit Jubin, Feb 24 2015: 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...... ---------------------------------------------- Bob Selcoe, Feb 25 2015: 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? ---------------------------------------------- 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. ----------------------------------------------