[seqfan] Re: Elimination game in a square of integers

Sat May 2 01:13:04 CEST 2020

On Fri, May 1, 2020 at 2:35 PM Allan Wechsler <acwacw at gmail.com> wrote:

> For the 1x1 board, the winner is 1.
> For the 2x2 board, the winner is 1 (ends on cell 3).
> For the 3x3 board, the winner is 3 (ends on cell 8).
> For the 4x4 board, I believe the winner is 2; king 2 ends on cell 8, and
> king 1 is still on the board at cell 15, but they cannot attack each other.
>

I agree with you. One can remark other patterns, e.g.,
- for n > 1, row 1 (and n-1 for odd n) are empty in the final position,
- for n >= 6, king number 2 always ends on field [2,4] (followed by
isolated 4, 6, ... for large enough n),
  number 1 sits on [3, 2], with an otherwise empty row 3.
- for odd n, the last row holds the (n-1)/2 largest odd numbers < (n-1)^2
except for (n-1)^2-3
 (for example, n=7 => last row is [0, 29, 0, 31, 0, 35, 0],
 for n=9, => [ 0, 55, 0, 57, 0, 59, 0, 63, 0 ], etc.)
 and there are no larger numbers, so in particular
 the winner is (n-1)^2-1 on the field [n, n-1].
- For even n = 2k > 4, the winner is number n^2-3 when k is odd and n^2-5
when k is even.

- Maximilian

Results from my PARI program below:
for(i=1,20,print(i " : " kings_battle(i))) \\ [number of winner,
co-ordinates, board]
1 : [1, [1, 1]~, [1]]
2 : [1, [2, 1]~, [0, 0 ; 1, 0]]
3 : [3, [3, 2]~, [0, 0, 0 ;* 0, 0, 0 ;* 0, 3, 0]]
4 : [2, [2, 4]~, [0, 0, 0, 0 *; 0, 0, 0, 2 ;* 0, 0, 0, 0 ;* 0, 0, 1, 0*]]
5 : [15, [5, 4]~, [0, 0, 0, 0, 0 ;* 0, 0, 0, 5, 0* ;
 0, 1, 0, 0, 0 ; *0, 0, 0, 0, 0* ; 0, 11, 0, 15, 0]]

6 : [33, [5, 2]~, [*0, 0, 0, 0, 0, 0 ;* 0, 0, 0, 2, 0, 4 ;* 0, 1, 0, 0, 0,
0 ;*
 0, 0, 0, 0, 0, 16 ;* 0, 33, 0, 0, 0, 0 ;* 0, 0, 0, 0, 15, 0]]

7 : [35, [7, 6]~, [*0, 0, 0, 0, 0, 0, 0 ;* 0, 0, 0, 2, 0, 7, 0 ;* 0, 1, 0,
0, 0, 0, 0 ;*
 0, 0, 0, 0, 0, 21, 0 ;* 0, 15, 0, 17, 0, 0, 0 ;* 0, 0, 0, 0, 0, 0, 0 ;* 0,
29, 0, 31, 0, 35, 0*]]

8 : [59, [7, 2]~, [*0, 0, 0, 0, 0, 0, 0, 0 ;* 0, 0, 0, 2, 0, 4, 0, 6 ;
 0, 1, 0, 0, 0, 0, 0, 0 ;* 0, 0, 0, 0, 0, 20, 0, 22 ;*
 0, 17, 0, 19, 0, 0, 0, 0 ;* 0, 0, 0, 0, 0, 0, 0, 38 ;*
 0, 59, 0, 51, 0, 0, 0, 0 ;* 0, 0, 0, 0, 0, 0, 37, 0*]]

9 : [63, [9, 8]~, [* 0, 0, 0, 0, 0, 0, 0, 0, 0 ;* 0, 0, 0, 2, 0, 4, 0, 9, 0
;* 0, 1, 0, 0, 0, 0, 0, 0, 0 ;*
 0, 0, 0, 0, 0, 22, 0, 27, 0 ;* 0, 19, 0, 21, 0, 0, 0, 0, 0 ;* 0, 0, 0, 0,
0, 0, 0, 45, 0 ;
* 0, 37, 0, 39, 0, 41, 0, 0, 0 ;* 0, 0, 0, 0, 0, 0, 0, 0, 0 ;* 0, 55, 0,
57, 0, 59, 0, 63, 0*]]

10: [97, [9, 6]~, [ *0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ;* 0, 0, 0, 2, 0, 4, 0,
6, 0, 8 ;
* 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ;* 0, 0, 0, 0, 0, 24, 0, 26, 0, 28,
* 0, 21, 0, 23, 0, 0, 0, 0, 0, 0 ;* 0, 0, 0, 0, 0, 0, 0, 46, 0, 48 ;
 *0, 41, 0, 43, 0, 45, 0, 0, 0, 0 ;* 0, 0, 0, 0, 0, 0, 0, 0, 0, 68 ;
 *0, 93, 0, 83, 0, 97, 0, 0, 0, 0 ;* 0, 0, 0, 0, 0, 0, 0, 0, 67, 0]]

11: [99, [11, 10]~, [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ;* 0, 0, 0, 2, 0, 4,
0, 6, 0, 11, 0 ;* 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ;
* 0, 0, 0, 0, 0, 26, 0, 28, 0, 33, 0 ;* 0, 23, 0, 25, 0, 0, 0, 0, 0, 0, 0 ; *0,
0, 0, 0, 0, 0, 0, 50, 0, 55, 0 ;*
 0, 45, 0, 47, 0, 49, 0, 0, 0, 0, 0 ; *0, 0, 0, 0, 0, 0, 0, 0, 0, 77, 0 ;* 0,
67, 0, 69, 0, 71, 0, 73, 0, 0, 0 ;
 *0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ;* 0, 89, 0, 91, 0, 93, 0, 95, 0, 99, 0]]

12: [139, [11, 6]~, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ;* 0, 0, 0, 2, 0,
4, 0, 6, 0, 8, 0, 10 ;*
 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ; *0, 0, 0, 0, 0, 28, 0, 30, 0, 32, 0,
34 ;*
 *0, 25, 0, 27, 0, 0, 0, 0, 0, 0, 0, 0 ;* 0, 0, 0, 0, 0, 0, 0, 54, 0, 56,
0, 58 ;
 *0, 49, 0, 51, 0, 53, 0, 0, 0, 0, 0 ; *0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 80,
0, 82 ;
 *0, 73, 0, 75, 0, 77, 0, 79, 0, 0, 0, 0 ;* 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 106 ;
* 0, 135, 0, 123, 0, 139, 0, 127, 0, 0, 0, 0 ;* 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 105, 0]]

13: [143, [13, 12]~, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ;* 0, 0, 0, 2,
0, 4, 0, 6, 0, 8, 0, 13, 0 ;* 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ;
* 0, 0, 0, 0, 0, 30, 0, 32, 0, 34, 0, 39, 0 ;* 0, 27, 0, 29, 0, 0, 0, 0, 0,
0, 0, 0, 0 ;* 0, 0, 0, 0, 0, 0, 0, 58, 0, 60, 0, 65, 0 ;*
 0, 53, 0, 55, 0, 57, 0, 0, 0, 0, 0, 0, 0 ; 0, 0, 0, 0, 0, 0, 0, 0, 0, 86,
0, 91, 0, 0, 79, 0, 81, 0, 83, 0, 85, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 117, 0,
 0, 105, 0, 107, 0, 109, 0, 111, 0, 113, 0, 0, 0 ; *0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0 ; *0, 131, 0, 133, 0, 135, 0, 137, 0, 139, 0, 143, 0]]

14; [193, [13, 10]~, [0 .. 0 ; *0, 0, 0, 2, 0, 4, 0, 6, 0, 8, 0, 10, 0, 12
;* 0, 1, 0..0 ;
 ... ;* 0, 185, 0, 171, 0, 189, 0, 175, 0, 193, 0, 0, 0, 0 ;* 0 .. 0, 151,
0]]

15: [195, [15, 14]~, [0 .. 0 ;* 0, 0, 0, 2, 0, 4, 0, 6, 0, 8, 0, 10, 0, 15,
0,*
 0, 1, 0, ...* 0, 165, 0 ;* 0, 151, 0, 153, 0, 155, 0, 157, 0, 159, 0, 161,
0, 0, 0,
* 0 ... 0 ;* 0, 181, 0, 183, 0, 185, 0, 187, 0, 189, 0, 191, 0, 195, 0]]

16: [251, [15, 10]~, [0 ... 0 ;* 0, 0, 0, 2, 0, 4, 0, 6, 0, 8, 0, 10, 0,
12, 0, 14 ;* 0, 1, 0 .. 0 ; ... ;
 0, 243, 0, 227, 0, 247, 0, 231, 0, 251, 0, 235, 0, 0, 0, 0 ; 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 205, 0]]

17: [255, [17, 16]~, [*0 ... 0 ;* 0, 0, 0, 2, 0, 4, 0, 6, 0, 8, 0, 10, 0,
12, 0, 17, 0 ;* 0, 1, 0 .. 0 ;*
 ...;* 0 ... 0 ;* 0, 239, 0, 241, 0, 243, 0, 245, 0, 247, 0, 249, 0, 251,
0, 255, 0]]

18: [321, [17, 14]~, [0 ... 0 ;* 0, 0, 0, 2, 0, 4, 0, 6, 0, 8, 0, 10, 0,
12, 0, 14, 0, 16 ;* 0, 1, 0 .. 0 ; ... ;
 0, 309, 0, 291, 0, 313, 0, 295, 0, 317, 0, 299, 0, 321, 0, 0, 0, 0 ; 0 ..
0, 267, 0]]

19: [323, [19, 18]~, [0 ... 0 ;* 2, 0, 4, 0, 6, 0, 8, 0, 10, 0, 12, 0, 14,
0, 19, 0 ;* 0, 1, 0 .. 0 ; 0, ..., 0, 285, 0 ;
* 0, 267, 0, 269, 0, 271, 0, 273, 0, 275, 0, 277, 0, 279, 0, 281, 0, 0, 0 ;*
0 ... 0 ;
 0, 305, 0, 307, 0, 309, 0, 311, 0, 313, 0, 315, 0, 317, 0, 319, 0, 323, 0]]
...

(PARI)
kings_battle(n)={my( N=n^2, K=[1..N] /*position of king i*/, board=K /*
king on field i */, i=N, coord(F)=divrem(F-1,n)+[1,1]~, done);
until( done, my( last=i ); until( i == last && done = 1 /*tried all
kings*/, K[ i = i%N+1 ] || next /*already taken*/;
 my( xy=coord(K[i]), m=0); /* see whether this  king can take any other one
*/
 forvec( d=vectorv(2,i,[-(xy[i]>1),xy[i]<n]), d && board[ K[i] + [n,1]*d
]>m && m = board[ K[i] + [n,1]*d ] );
 m || next; /* we can take king m */; board[ K[i] ] = 0/*empty*/; K[i] =
K[m]; K[m]=0/*dead*/; board[ K[i]] = i; next(2)));
i=vecmax(board); [i,coord(K[i]), board] }

>
> On Fri, May 1, 2020 at 1:29 PM Nacin, David <NACIND at wpunj.edu> wrote:
>
> > Meant to include a
> >
> > 7 takes out 4
> >
> > in there as well before I couldn't proceed.
> >
> > -David
> > ________________________________
> > From: Nacin, David <NACIND at wpunj.edu>
> > Sent: Friday, May 1, 2020 1:12 PM
> > To: Sequence Fanatics Discussion List <seqfan at list.seqfan.eu>
> > Cc: Ali Sada <pemd70 at yahoo.com>
> > Subject: Re: [seqfan] Elimination game in a square of integers
> >
> > Are we having the king jump over removed squares?  Otherwise I can only
> > follow your directions up to
> >
> > 1 takes out 5
> > 2 takes out 6
> > 3 takes out 2
> > 4 takes out 8
> >
> > and then we have a 1,3,7 and 9 which aren't adjacent to each other.
> >
> > Best,
> >
> > -David
> > ________________________________
> > From: SeqFan <seqfan-bounces at list.seqfan.eu> on behalf of Ali Sada via
> > SeqFan <seqfan at list.seqfan.eu>
> > Sent: Friday, May 1, 2020 12:22 PM
> > To: Sequence Fanatics Discussion List <seqfan at list.seqfan.eu>
> > Cc: Ali Sada <pemd70 at yahoo.com>
> > Subject: [seqfan] Elimination game in a square of integers
> >
> > Hi Everyone,
> > We take the numbers from 1 to n^2 and put them in a square. Starting with
> > 1, and moving as a chess king, each number in its tern takes out the
> > largest number it can get.
> > a(n) is the largest remaining number.
> >
> > For example, in a 3 by 3 square we have the following moves:
> > 1 takes out 5
> > 2 takes out 6
> > 3 takes out 2
> > 4 takes out 8
> > 7 takes out 4
> > 9 takes out 7
> > 1 takes out 9
> > and 3 takes out 1.
> > a(3) = 3
> >
> >
> > I usually make mistakes when I calculate the terms, so I would really
> > appreciate it if you could help me with this. I would love to know if
> there
> > is a pattern here. Also, I want to check if this is a suitable sequence
> for
> > the OEIS.
> >
> > Best,
> >
> > Ali
>