login
A358339
Array read by antidiagonals upwards: A(n,k) is the number of nonequivalent positions in the KRvK endgame on an n X n chessboard with DTM (distance to mate) k, n >= 3, k >= 0.
0
2, 4, 5, 3, 15, 9, 5, 10, 36, 13, 9, 51, 21, 70, 20, 5, 30, 122, 36, 120, 27, 4, 40, 59, 231, 55, 189, 35, 0, 26, 97, 101, 384, 78, 280, 44, 0, 30, 39, 181, 165, 587, 105, 396, 54, 0, 31, 87, 53, 311, 246, 846, 136, 540, 65, 0, 22, 79, 134, 67, 484, 356, 1167, 171, 715, 77
OFFSET
3,1
COMMENTS
DTM (distance to mate) is measured in ply (half-moves), equivalence is under action of the square's symmetry group (D_4), however colors can't be swapped because one side always has a rook.
A225552(n) is the maximum value of k such that A(n,k)!=0, divided by 2 because it's in moves instead of ply (though each column seems to terminate at an even (losing) k, so perhaps no information is lost).
In each column, there are n-2 positions counted (in which the king without the rook is to move) that are orphans (with no predecessors), each represented by a horizontally-shifted version of the piece configuration (Ka1 - Kc2 Rc1) (in which the rook is blocked from having been moved downwards (to cause the check) by its king, that could not have exited from in front without having been adjacent to the king to move). Each one's DTM corresponds with the distance of the king to move from the corner in the opposite direction from the other king, DTM is 4 when on a1, 12 when on b1, 18 when on c1, 22 when on d1, 28 when on e1, and increasing by 2 for all thereafter.
Positions with the side with the king to move at a1, its rook at b1 and the opponent king at (ceiling(n/2),ceiling(n/2)) seem to be wins in 4*n - 6 + 2*floor((n+1)/2) - 2*floor(n/6).
.
For fixed values of n, all values A(n,k) with odd k (winning positions) seem to exceed A(n,k-1) and A(n,k+1) (losing positions) until a threshold value, beyond which this relationship inverts.
For all k, A(n,k)/Sum_{k>=0}(A(n,k)) is o(1) over n (for n>=A225552^(-1)(2*k)), so there is no k such that the polynomial eventually describing A(n,k) is of degree 6, and for all j, Sum_{k=0..j}(A(n,k)) is o(Sum_{k>=0}(A(n,k))).
For each k, there exists a polynomial eventually describing A(n,k) over n, though there can be arbitrarily many leading zero terms so it can take arbitrarily long to do so. Note that it is not necessarily an upper bound.
All polynomials for k >= 7 are quadratic.
.
Conjecture 1: If A(n+1,k) is nonzero, it is always greater than A(n,k).
Conjecture 2: As the increments to A225552 become periodic for n>24, so too do the differences between successive polynomials over n for each k>108, and for all j, Sum_{k=2*A225552(n)-j..2*A225552(n)}(A(n,k)) is o(Sum_{k>=0}(A(n,k))) (the same equation from the opposite side).
Conjecture 3: (Begin)
Note that Sum_{k>=0}(A(n,k)-A(n-1,k)) ~ 3*n^5/2. (See FORMULA for the exact form.)
For all n, assuming conjecture 2, because the polynomials provide upper bounds and all are of degree <=5, it is necessary for the sum of all nonzero A(n,k)'s polynomials (for k<=2*A225552(n)) to have n^2 coefficients summing to 3*n^4/2.
A225552(n) ~ 7*n/3 (and seems to become periodic for n>24), so the number of elements added with each increment of n is ~ 14/3.
Thus, for n>24, the change of 3/2 to the sum of n^5 coefficients with each increment to n causes each new term's eventual polynomial to have an n^2 term with a coefficient asymptotic to (3/2)/(14/3)*n^2=9*n^2/28.
(End)
Conjecture 4: The function o (defined in the FORMULA section), for each parity of k, contains only polynomials over n (without any terms with coefficients of n%2 or (-1)**n). For all m>=3, there exists a pair of polynomials over n (for even and odd k), such that when o adds them to the output of the k-specific fitting polynomial for n=k-m, the values returned are correct for all k>=5*(m-1). (Works for m=2,3,4.) Equivalently, for all k>10, while A(n,k) can be described exactly by a k-specific polynomial over n for all n>=A052928(k), it can be described exactly by the sum of that and a (2*k-n)-specific polynomial over n (or equivalently, over k) for all n>=k-1-floor(k/5).
LINKS
Vaclav Kotesovec, King and Two Generalised Knights against King, ICGA Journal, Vol. 24, No. 2, pp. 105-107 (2001).
Vaclav Kotesovec, Fairy chess endings on an n x n chessboard, Electronic edition of chess booklets by Vaclav Kotesovec, vol. 8, pp. 360-361 (2013).
Ronald de Man, Bojun Guo, and Niklas Fiekas, KRvK.json, syzygy-tables.info
FORMULA
Sum_{k>=0}(A(n,2*k)) = (n^6 - 19*n^4 + 27*n^3 + 93*n^2 - 242*n + 112 + (-n^3+7*n^2-18*n+16)*(-1)^n)/8. (losing/checkmated positions)
Sum_{k>=0}(A(n,2*k+1)) = (n-2)*(n-1)*(3*n^4 + 3*n^3 - 22*n^2 + 19*n - 15 + (3-n)*(-1)^n)/24. (winning positions)
Sum_{k>=0}(A(n,k)) = (6*n^6 - 6*n^5 - 82*n^4 + 172*n^3 + 163*n^2 - 643*n + 306 + (2-n)*(4*n^2 - 19*n + 27)*(-1)^n)/24.
Note that for n>=3, there are n+1 nonequivalent positions that are stalemates, each one with the king to move at a1 (under symmetry), 2 with the rook on b2 and its king on c2 or c3, and n-1 with the other at c1 and the rook in one of the squares on the second rank and file >= b.
There are also (n-2)*(4*n^3 + 2*n^2 - 43*n + 31 + (3-n)*(-1)^n)/4 positions in which the rook can be immediately captured (making it unwinnable) that are not included in the sequence, and A357723(n) in the resulting KvK endgame.
The winning positions are those in which the side with the rook is to move, but to get the number in which the side without the rook is to, adding the losing and stalemated positions yields (n-2)*(n^5 + 2*n^4 - 15*n^3 - 3*n^2 + 87*n - 60 - (n^2 - 5*n + 8)*(-1)^n)/8, then adding yields (n-2)*(n-1)*(n^4 + 3*n^3 - 4*n^2 - 3*n - 2 + (2-n)*(-1)^n)/8, so the equations for each side to move both have roots at n=1 and n=2.
In total, there are (n-2)*(n-1)*(6*n^4 + 12*n^3 - 34*n^2 + 10*n - 21 + (-4*n+9)*(-1)^n)/24 nonequivalent positions in the KRvK endgame.
Sum_{k>=0}(A(n,k)-A(n-1,k)) = (18*n^5 - 60*n^4 - 74*n^3 + 429*n^2 - 226*n - 282 + (-4*n^3 + 33*n^2 - 98*n + 102)*(-1)^n)/12.
.
The values of n at which each value of k begins to abide by a polynomial are ((2,1,2,4,6,5,5,6,8,7)[k] if k<10 else (floor(k/2)*2 = A052928(k))). This value can be changed (reduced for k>=10) to ((2,1,1,4,6,5,6,5,7,7,7,8,9,9,11,11,12,13,14,15)[k] if k<20 else k-5) by adding the output of the following function to each polynomial at each value (offsetting only 5-k%2 values):
define o(n,k):
.if k is odd:
..if n=k-2:
...add (n-1)/2-3
..else if n=k-3:
...add n-4
..else if n=k-4:
...add n^2-n-15
..else if n=k-5:
...add 3*n^2-(9*n+23)/2
.else:
..if k-n=1:
...add (n-1)/2-1
..else if n=k-2:
...add n-1
..else if n=k-3:
...add 4*n-15
..else if n=k-4:
...add 8*n-35
..else if n=k-5:
...add (25*n-137)/2
.
A(n, k) = 0 if n<3 or k>2*A225552(n).
The sequence measures distance to mate, as is convention in chess (so A(n,0) counts positions in checkmate), however if kings were to be allowed to be captured, the number of positions after a move into check from a position in checkmate (usually considered illegal) would be
A(n,-1) = (n-1)*(6*n^4 + 22*n^3 - 60*n^2 + 59*n - 24 + (n-2*n^2)*(-1)^n)/24
(note that (n-1)*(4*n + 1 - (-1)^n)/4 of these cases have the rook captured)
A(n, 0) = 0 if n<2 else (n-2)*(n+1)/2 = n^2/2 - n/2 - 1 = A000096(n-2).
A(n, 1) = 0 if n<1 else (n-2)*(n-1)*(n+1)/2 = n^3/2 - n^2 - n/2 + 1 = A077414(n-1).
A(n, 2) = 0 if n<2 else (n-2)*(2*n-3) = 2*n^2 - 7*n + 6 = A014105(n-2).
A(n, 3) = (0,0,0,5)[n] if n<4 else n^3 + 4*n^2 - 26*n + 27 = m^3 - 94*m/3 + 1793/27, where m = n + 4/3.
A(n, 4) = (0,0,0,9,30,59)[n] if n<6 else (2*n^3 - 5*n + 5 + (3-n)*(-1)^(n))/4
A(n, 5) = (0,0,0,5,40)[n] if n<5 else (6*n^3 - 26*n^2 + 84*n - 135 + (7-2*n)*(-1)^n)/4 = 3*m^3/2 + 209*m/18 - 12109/972 + (m/2-37/36)*(-1)^n, where m = n - 13/9.
A(n, 6) = (0,0,0,4,26)[n] if n<5 else 14*n - 31.
A(n, 7) = (0,0,0,0,30, 87)[n] if n<6 else 2*n^2 + 24*n - 82.
A(n, 8) = (0,0,0,0,31, 79,116)[n] if n<7 else 2*n^2 + 14*n - 42 + o().
A(n, 9) = (0,0,0,0,22,174,310)[n] if n<7 else 11*n^2 - 7*n - 41.
A(n,10) = (0,0,0,0,65,178,262)[n] if n<7 else 7*n^2 + 7*n - 40 + o(n,10).
A(n,11) = (0,0,0,0, 7,180,492, 795)[n] if n<8 else 45*n^2/2 - 73*n/2 - 61 + o(n,11).
A(n,12) = (0,0,0,0,25,206,291, 449, 592)[n] if n<9 else 9*n^2 + 7*n - 64 + o(n,12).
A(n,13) = (0,0,0,0, 2,125,461,1002,1418)[n] if n<9 else (53*n^2 - 75*n)/2 - 58 + o(n,13).
A(n,14) = (0,0,0,0, 6,243,397, 552, 683, 805, 939)[n] if n<11 else (7*n^2 + 141*n)/2 - 160 + o(n,14).
A(n,15) = (0,0,0,0, 0, 49,447,1147,2149,2950,3709)[n] if n<11 else (91*n^2 - 205*n)/2 - 44 + o(n,15).
A(n,16) = (0,0,0,0, 0,136,619, 986,1433,1836,2254,2559)[n] if n<12 else (39*n^2 + 47*n)/2 - 134 + o(n,16).
A(n,17) = (0,0,0,0, 0, 19,473,1303,2514,4166,5703,6973,8306)[n] if n<13 else (139*n^2 - 341*n)/2 - 16 + o(n,17).
A(n,18) = (0,0,0,0, 0, 70,698,1207,1712,2376,3075, 3578, 4197, 4690)[n] if n<14 else (49*n^2 + 97*n)/2 - 179 + o(n,18).
A(n,19) = (0,0,0,0, 0, 2,292,1154,2382,4296,6722, 8563,10691,12530,14445)[n] if n<15 else (171*n^2 - 389*n)/2 - 94 + o(n,19).
A(n,20) = (0,0,0,0, 0, 7,782,1515,1985,2624,3532, 4518, 5466, 6308, 7261)[n] if n<15 else 34*n^2 + 42*n - 302 + o(n,20).
A(n,21) = (0,0,0,0, 0, 0, 96,1124,2565,4341,7182,10310,13031,15307,18270,20921)[n] if n<16 else 106*n^2 - 262*n + 6 + o(n,21).
A(n,22) = (0,0,0,0, 0, 0,313,2116,2854,3322,4186, 5212, 6278, 7313, 8479, 9494,10681)[n] if n<17 else 35*n^2 + 106*n - 358 + o(n,22).
A(n,23) = (0,0,0,0, 0, 0, 13, 832,2691,5011,7578,11884,16461,19759,23062,26187,30474,34401)[n] if n<18 else 133*n^2 - 306*n - 194 + o(n,23).
A(n,24) = (0,0,0,0, 0, 0, 45,2002,3597,5172,6558, 7114, 8891,10534,11965,13623,15618,17470,19443)[n] if n<19 else (109*n^2 + 223*n)/2 - 687 + o(n,24).
A(n,25) = (0,0,0,0, 0, 0, 0, 258,2234,5482,9412,13305,20056,25698,30163,33982,39027,43570,49523,55256) if n<20 else (345*n^2 - 931*n)/2 + 60 + o(n,25).
A(n,26) = (0,0,0,0, 0, 0, 0, 773,4194,6209,8937,10557,12341,13901,15940,18224,20672,23119,25666,28471,31426) if n<21 else 75*n^2 + 73*n - 589 + o(n,26).
EXAMPLE
Array begins (transposed):
k\n| 3 4 5 6 7 8 9 10 11 ...
----+---------------------------------------------
0 | 2 5 9 14 20 27 35 44 54
1 | 4 15 36 70 120 189 280 396 540
2 | 3 10 21 36 55 78 105 136 171
3 | 5 51 122 231 384 587 846 1167 1556
4 | 9 30 59 | 101 165 246 356 487 655
5 | 5 40 | 97 181 311 484 725 1023 1411
6 | 4 26 | 39 53 67 81 95 109 123
7 | 0 30 87 | 134 184 238 296 358 424
8 | 0 31 79 116 156 | 198 246 298 354
9 | 0 22 174 310 | 449 607 787 989 1213
10 | 0 65 178 262 365 471 593 | 730 884
11 | 0 7 180 492 795 1097 1434 | 1824 2260
...
(where vertical lines denote indexes at which the rows for fixed k begin to abide by polynomials)
The following diagrams are positions counted. Pieces with uppercase letters are next to move.
.
A(3,0)=2:
|r |r |
| | k|
|K k|K |
.
A(3,1)=4:
| R |R |k |k |
| | | R| |
|K k|K k| K | KR|
.
A(3,2)=3:
|k r| kr| k |
| | | r|
| K | K | K |
.
A(3,3)=5:
| R |R | | k | k |
| k| k| k|R | |
|K |K |KR | K |RK |
.
A(3,4)=9:
| r| r | | r| r | | | rk|r k|
| | | | k| k| k| k| | |
|K k|K k|Krk|K |K |K r|Kr |K |K |
.
A(3,5)=5:
| | | k| k|k |
| R |R | R | | R |
|K k|K k|K |KR | K |
.
A(3,6)=4:
|kr |k |k | k |
| | r |r | r |
| K | K | K | K |
CROSSREFS
Nonzero column lengths: A225552, nonequivalent KvK positions: A357723.
Rows k=0..2: A000096(n-2), A077414(n-1), A014105(n-2).
Sequence in context: A376733 A332667 A266408 * A230564 A011174 A123545
KEYWORD
nonn,tabl
AUTHOR
Nathan L. Skirrow, Nov 10 2022
STATUS
approved