9
$\begingroup$

Ana and Bob alternately write Xs on a 2022 × 1 board. The winner is the one who makes 3 consecutive Xs. Who has the winning strategy if Ana plays the first move? Describe such a strategy.

$\endgroup$
11
$\begingroup$

This game is also known as Treblecross.

There is a neat way to think about this game. As soon as you place an X next to another X, or one away from another X you lose because the opponent can make three in a row. Therefore the Xs need to be a distance of at least 2 apart. You can think of each X being in the middle of a 3x1 bar that you place on the board, where you don't want the bars to overlap. To allow an X to be placed at the outer ends, extend the board with an extra square on each side. In this view the board consists of one or more empty regions, and if you place a piece in a region of length n you split it into two regions of lengths a and b such that n=a+b+3, and one or both of a and b are allowed to be zero.

This is kind of Nim game called an octal game, in particular the one with signature 0.007 which is also known as the James Bond game for obvious reasons.

As with all Nim games, you can recursively assign each board size a nim-value. This is easily done by computer, but unfortunately this particular game's nim values do not show a simple repeating pattern so there is little chance of a human being able to play this game optimally. Apparently the Bond game has been computed up to size $2^{28}$ without finding a repeating pattern, though it is conjectured that all finite octal games like this one do eventually repeat.

Below is a table of all the Nim values for regions of size up to 2029. The value of the empty (extended) board of size 2024 is 10, so Ana should be able to win. And indeed, she can place her 3x1 piece to split the length 2024 board into regions of size 152 and 1869, which both have nim value 9 (and so have a combined nim value of 9 xor 9 = 0).

To play optimally, you have to be able to calculate the total nim-value of the current board. So you have to look up the nim-value for each region in the table below, combine them using a bitwise exclusive Or operation, and the result is the current value of the board. A winning move will cause the board's nim value to become zero. If the board has a non-zero nim-value, then there is always some winning move available. If it is already zero then there is no winning move, as all moves will make the nim-value non-zero.

Almost all the board sizes have a non-zero nim value, which means that Ana will win. The board sizes with a zero nim-value, the ones where Bob will win, are:

0 1 2 8 14 24 32 34 46 56 66 78 88 100 112 120 132 134 164 172 186 196 204 284 292 304 358 1048 2504 2754 2914 3054 3078 7252 7358 7868 ...

Here is the table:

   0:   0   0   0   1   1   1   2   2   0   3
  10:   3   1   1   1   0   4   3   3   3   2
  20:   2   2   4   4   0   5   5   2   2   2
  30:   3   3   0   5   0   1   1   1   3   3
  40:   3   5   6   4   4   1   0   5   5   6
  50:   6   2   7   7   7   8   0   1   9   2
  60:   7   2   3   3   3   9   0   5   4   4
  70:   8   6   6   2   7   1   1   1   0   5
  80:   5   9   3   1   8   2   8   5   0   1
  90:   1   12  2   2   7   3   3   9   4   4
 100:   0   11  3   3   3   9   2   2   8   1
 110:   3   5   0   9   12  2   6   13  13  5
 120:   0   1   1   4   11  7   7   10  3   4
 130:   1   4   0   5   0   3   3   6   7   2
 140:   14  13  10  4   12  9   2   2   3   3
 150:   6   9   9   1   16  4   8   3   3   2
 160:   15  1   1   4   0   5   5   16  6   6
 170:   6   8   0   16  5   4   4   17  2   2
 180:   7   14  6   10  12  1   0   16  13  3
 190:   6   2   7   7   8   1   0   5   17  2
 200:   12  15  3   11  0   19  18  12  4   16
 210:   17  2   2   21  6   9   4   19  5   5
 220:   17  10  3   6   19  2   7   8   4   1
 230:   9   12  7   2   13  6   3   19  5   9
 240:   4   8   8   17  17  2   15  18  1   1
 250:   8   5   21  16  21  3   19  19  13  5
 260:   18  1   4   17  7   2   7   6   3   19
 270:   12  5   5   16  16  6   17  19  7   7
 280:   18  1   4   17  0   9   16  3   3   14
 290:   13  22  0   1   15  24  17  2   6   18
 300:   3   4   19  19  0   8   21  16  3   15
 310:   7   26  18  13  1   1   17  9   2   21
 320:   2   6   22  19  9   5   16  4   16  20
 330:   3   7   18  23  22  8   20  5   16  21
 340:   15  6   10  19  18  18  18  4   4   17
 350:   17  7   2   3   23  19  9   5   0   16
 360:   16  3   17  30  2   18  18  8   4   17
 370:   17  9   27  6   10  19  19  14  9   9
 380:   4   20  17  14  11  7   18  6   19  19
 390:   5   13  16  16  10  6   19  19  23  18
 400:   4   4   17  12  12  14  10  6   3   19
 410:   5   9   5   21  16  20  6   7   7   18
 420:   30  13  13  17  12  21  15  10  3   19
 430:   22  18  8   4   32  17  17  11  14  6
 440:   26  24  12  5   9   16  16  6   7   7
 450:   7   18  18  8   4   17  20  7   16  10
 460:   10  22  19  22  9   23  4   13  17  20
 470:   7   11  23  23  4   5   9   5   16  16
 480:   10  17  10  22  18  23  8   4   17  17
 490:   20  16  32  13  19  19  33  5   5   24
 500:   8   17  20  33  18  18  23  13  22  33
 510:   33  16  15  10  10  19  19  33  18  8
 520:   20  17  17  11  16  18  26  22  19  12
 530:   9   16  16  34  20  17  35  23  18  8
 540:   8   8   17  33  16  32  10  11  22  11
 550:   12  23  9   8   17  17  11  33  18  18
 560:   19  13  12  21  16  16  10  20  14  11
 570:   22  23  34  8   17  17  29  16  7   34
 580:   19  19  9   23  5   8   32  17  33  11
 590:   23  18  18  8   12  12  16  16  16  10
 600:   32  22  22  11  18  13  8   20  17  11
 610:   21  11  15  19  22  12  12  16  16  32
 620:   17  17  35  23  18  8   13  13  9   17
 630:   16  10  10  19  14  19  25  12  12  13
 640:   20  14  11  11  23  10  22  22  35  9
 650:   16  16  17  10  20  11  18  18  13  13
 660:   24  17  12  16  15  34  19  19  33  12
 670:   16  32  8   17  20  33  18  10  18  32
 680:   24  8   16  16  16  15  32  19  19  22
 690:   13  13  32  20  20  35  33  34  15  22
 700:   19  12  12  13  13  21  20  14  14  18
 710:   18  23  22  13  9   17  16  15  15  10
 720:   11  19  18  12  12  8   20  17  11  21
 730:   15  15  31  12  38  13  25  8   20  10
 740:   15  11  23  18  13  13  12  12  12  21
 750:   32  10  19  19  9   9   38  13  20  17
 760:   14  11  14  27  18  5   12  13  1   21
 770:   16  17  17  19  11  11  18  13  8   12
 780:   24  20  16  11  15  19  19  12  9   13
 790:   13  13  33  17  14  3   15  32  19  8
 800:   9   4   16  15  32  19  19  11  33  18
 810:   32  17  17  14  14  33  18  10  19  12
 820:   35  33  16  16  15  26  10  11  23  18
 830:   13  13  20  20  20  16  37  34  22  19
 840:   23  18  25  8   17  17  11  11  18  10
 850:   10  19  40  36  9   16  16  15  32  11
 860:   6   18  18  13  8   17  9   35  16  34
 870:   10  19  19  31  35  9   21  13  20  14
 880:   10  18  18  23  34  41  12  4   16  32
 890:   5   26  11  14  18  13  12  8   20  17
 900:   16  16  23  15  19  19  35  40  16  16
 910:   20  17  46  14  11  18  34  8   12  17
 920:   20  16  32  39  19  22  31  23  9   8
 930:   8   21  17  33  15  10  10  22  19  12
 940:   21  16  20  15  32  35  11  18  18  34
 950:   13  9   29  16  21  11  14  19  19  35
 960:   35  16  8   17  20  33  14  11  10  30
 970:   13  44  40  1   16  28  32  44  19  11
 980:   23  23  9   32  17  17  21  16  49  2
 990:   22  40  35  33  16  8   34  17  43  10
1000:   18  18  39  22  9   9   16  21  37  14
1010:   26  19  33  18  27  32  8   24  24  33
1020:   18  32  10  19  38  12  16  16  16  17
1030:   43  10  5   18  18  39  9   17  17  35
1040:   16  47  37  22  19  35  23  40  0   8
1050:   17  33  38  18  15  39  34  22  9   16
1060:   25  21  15  22  14  11  18  45  9   40
1070:   17  20  36  33  15  10  22  19  35  35
1080:   16  16  17  20  46  45  30  18  23  34
1090:   9   12  21  16  43  32  19  19  42  38
1100:   18  32  8   24  24  33  18  18  15  22
1110:   26  50  33  16  16  15  17  46  6   18
1120:   18  39  57  48  17  35  49  49  14  22
1130:   19  38  23  13  16  16  17  36  14  11
1140:   10  32  19  41  52  21  25  24  32  24
1150:   14  14  18  30  51  9   8   17  36  16
1160:   11  19  19  19  35  49  16  13  29  53
1170:   53  36  10  18  34  34  9   9   9   20
1180:   52  37  14  19  22  23  30  40  20  17
1190:   36  21  36  32  18  19  31  55  33  21
1200:   16  37  17  35  23  30  18  34  48  12
1210:   24  35  49  49  44  22  19  22  18  35
1220:   34  8   20  29  47  18  23  30  55  22
1230:   38  8   21  28  20  11  26  14  18  51
1240:   56  40  12  17  16  21  52  14  26  19
1250:   35  54  44  8   20  32  33  60  10  10
1260:   23  22  48  35  16  16  57  37  14  31
1270:   30  18  18  43  20  17  17  42  33  10
1280:   34  19  19  50  56  16  12  37  20  53
1290:   23  23  26  44  56  48  12  25  16  49
1300:   34  19  14  38  45  49  39  16  12  48
1310:   10  15  27  15  39  55  55  4   13  16
1320:   64  24  58  36  47  30  63  12  9   12
1330:   33  49  51  14  10  19  23  56  49  12
1340:   16  17  58  38  33  18  18  22  34  35
1350:   21  8   16  29  50  31  15  38  51  64
1360:   12  12  24  61  15  37  23  19  55  35
1370:   61  8   16  17  53  53  10  18  10  41
1380:   56  45  40  21  28  16  65  55  19  22
1390:   54  23  44  12  17  24  40  32  54  27
1400:   14  50  62  13  8   28  43  17  55  10
1410:   23  30  56  37  24  17  13  16  52  37
1420:   14  14  23  18  49  9   16  20  47  60
1430:   23  10  11  64  19  38  38  8   16  64
1440:   20  48  27  19  56  51  20  24  24  28
1450:   16  37  14  14  26  35  65  25  9   21
1460:   20  64  65  10  23  69  66  53  40  16
1470:   16  49  66  26  19  19  23  18  39  9
1480:   9   70  65  45  18  14  22  19  65  25
1490:   16  16  12  17  47  36  15  18  34  64
1500:   24  13  56  49  61  37  19  10  23  68
1510:   56  44  12  17  53  67  30  27  18  55
1520:   39  45  21  16  16  44  66  53  15  15
1530:   23  54  64  20  47  17  21  52  14  14
1540:   22  74  65  49  12  9   20  53  42  18
1550:   19  74  31  38  8   13  13  17  66  66
1560:   19  15  54  51  71  17  17  20  16  67
1570:   46  14  14  50  47  38  16  9   12  17
1580:   53  65  10  18  71  31  57  20  17  28
1590:   61  69  14  19  10  18  44  52  17  9
1600:   72  72  63  18  23  14  22  38  21  8
1610:   12  41  74  55  19  18  67  64  14  9
1620:   65  8   68  51  11  11  14  42  65  56
1630:   12  16  29  40  65  10  63  11  71  62
1640:   60  16  21  25  41  62  59  15  10  18
1650:   71  64  9   8   15  68  54  14  19  19
1660:   42  67  54  25  12  57  55  68  18  18
1670:   46  73  60  13  20  13  52  69  19  59
1680:   10  10  58  71  17  12  24  40  58  18
1690:   18  11  19  45  16  16  9   17  20  62
1700:   10  23  30  11  14  17  8   65  56  16
1710:   46  11  18  10  15  49  12  9   29  57
1720:   68  49  18  11  14  48  57  21  16  25
1730:   75  74  59  26  10  78  11  12  16  17
1740:   8   68  18  14  11  19  15  70  35  64
1750:   9   9   53  65  58  18  31  46  53  20
1760:   8   16  81  64  45  19  15  10  54  71
1770:   12  48  29  13  65  36  22  14  19  47
1780:   16  16  12  12  57  62  65  18  18  46
1790:   66  50  17  8   8   56  64  19  10  10
1800:   30  76  16  9   17  45  65  23  18  11
1810:   11  48  70  21  16  25  72  62  59  68
1820:   10  18  71  20  20  13  13  25  33  64
1830:   22  27  10  67  66  9   9   9   60  18
1840:   18  18  22  38  48  17  8   25  52  69
1850:   62  65  10  10  63  76  69  9   8   13
1860:   78  81  18  11  48  62  65  16  12  9
1870:   29  74  65  10  14  11  66  53  17  8
1880:   8   81  9   22  19  10  10  83  21  89
1890:   17  9   68  81  58  18  59  47  72  67
1900:   21  9   66  69  59  19  30  26  71  20
1910:   17  8   21  44  78  22  12  10  79  51
1920:   51  38  17  20  60  68  18  11  18  11
1930:   59  17  28  8   81  9   55  19  15  58
1940:   58  36  16  17  13  67  63  49  18  71
1950:   47  15  61  21  9   12  57  82  68  63
1960:   11  64  66  57  77  8   49  56  12  22
1970:   19  18  27  81  83  75  20  45  65  44
1980:   65  11  14  59  15  13  16  56  25  76
1990:   62  22  10  15  66  66  17  8   8   41
2000:   9   69  12  30  79  70  16  38  9   17
2010:   8   13  18  18  75  62  19  67  89  16
2020:   9   9   80  50  10  10  36  11  20  17
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.