4
$\begingroup$

Two players, Alice and Beatrice, having previously agreed on a positive integer N (say 30) as a limit, take turns to write a sequence of positive integers. In the first turn Alice writes 1. Thereafter, on the nth turn, whosoever turn it is, writes the previous term plus or minus n, or, if neither of these, the previous term times n, or divided by n (if the result is an integer). However, at no point must an integer in the sequence be repeated or exceed the limit agreed upon. The first player unable to play loses.

Here a game (with limit 30) won by Beatrice:

1, 3, 6, 10, 2, 8, 15, 23, 14, 4, ?

  1. If the agreed limit is indeed 30, what is the length of the longest possible game? Shortest?

  2. And being 30 the limit, does any of the two players have a winning strategy?

  3. In general, what is the length of the largest and shortest possible games if the limit is N? For which N, if any, does Alice have a winning strategy?

Notice that the resulting sequences are those mentioned here: Introducing S-sequences: which is the shortest to contain all integers 1 to 20?.

$\endgroup$

1 Answer 1

6
$\begingroup$
  1. Shortest and longest games?

1 3 9 13 18 12 05 (7 turns)
1 2 5 20 15 21 28 (7 turns)
1 2 5 20 15 21 14 22 13 23 12 24 11 25 10 26 09 27 08 28 07 29 06 30 (24 turns)

  1. Who wins this game with a limit of 30?

 Bob can always win.

 A  B  A  B  A  B  A  B  A  B  A  B
                      |     |     |
            14-08-15-23     |     |
           /                |     |
      05-09                 |     |
     /     \                |     |
    /       04-24-17-25-16-06     |
 1-2                              |
    \       19-13-20-28           |
     \     /                      |
      06-24       30-22-13-03-14-26
           \     /                |
            29-23                 |
                 \                |
                  16-08-17-27     |
                            |     |
 A  B  A  B  A  B  A  B  A  B  A  B

 Showing all of Alice's options, given Bob's winning plays.

  1. Length of longest/shortest games and who wins with optimal play for N from 1 to 200

Red: Longest game
Blue: Shortest game
Green: Alice wins (64)
Yellow: Bob wins (136)
enter image description here

$\endgroup$
2
  • $\begingroup$ A programmed search found 163 distinct complete games. The winning play was evaluated manually by examining the output. $\endgroup$ Mar 27, 2023 at 23:08
  • $\begingroup$ Fantastic results! $\endgroup$ Mar 29, 2023 at 2:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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