Think and deduce optimal strategy move for both Alice and Bob

combinatoricselementary-number-theorygame theoryrecreational-mathematics

Question:

Alice and Bob are playing a game on a one-dimensional number line. Initially, Alice is standing at coordinate $x=a$ (integer) and Bob is standing at $x=b$ (integer) .It is guaranteed that $a<b$.
Alice starts the game by playing the first move.
On a turn, a player chooses to move either 0, 2 or 3 units towards their opponent. However, the move must be different from the last move played by them. Both players have all three choices for their first move.
The game ends when either:

A player lands on the spot currently occupied by their opponent. The player is declared the winner in this case.

A player crosses their opponent and lands beyond them. The opponent is declared the winner in this case.

Given the starting positions of Alice and Bob, determine who wins the game if both of them play optimally.

My progress:
What I believed was that there might be a pattern on who might win the game giving a specific distance modulo some number. So let's say distance is $d$.

ALICE mindset: As Alice starts first, she wants to maximise all her chance of winning so she calculates all move possible in the beginning which would give her a better win chance.
As I don't have a way to think of what will happen for all the possible cases, I started with a move by Alice as 0.

BOB mindset:
Now since Bob too wants to maximise his chance of winning, so now he calculates all possible scenarios and consider the best move, I supposed he choosed also 0 .
Now next move by Alice should be either 2 or 3. I now realized that if $d$ was 5, then surely Bob would win since Alice whatever she do, Bob can just do a move of $5-$the move Alice did. So I thought maybe this would be the case for all distances of form $5k$, but I don't have a proof. If $d$ was 4, then I think Bob would win surely since 2 can be the move for A then B would do 2 too. Similarily considering for $d =1 ,2 ,3$ but not sure how to generalize for $d>5$ .

In all, my query is how to think of what's the optimal strategy for each player to follow always and why so? Also explain why the strategy of yours is optimal too.

this problem was a part of this https://codeforces.com/gym/445869/problem/F
i am just asking the mathematical portion.

like for the case of b-a being 1 its given bob wins as well as for the case of b-a being 5 and 6. but for b-a =94 its given that alice wins
the site problem in case anyone needs:

"the move must be different from the last move played by them", this means they must play a move different from the last move played by them only as in if A plays 0 then in next move A can only play 2,3 , similarly for B too . as in if B move 2 then next it can only play among 0,3

**it seems like the answer is this :
for d=1 Bob wins ;

for d==2 Alice wins;

for d>=3 and d is 3, 4congruent mod 5 then Alice wins ;

for d>=3 and rest cases Bob wins . **
can anyone prove this ?

Best Answer

Disclaimer

This question is poorly written by the author(s), since it leaves room for interpretation of the rules. The first part of this answer is based on the interpretation that "the move must be different from the last move played by them" means that apart from both player's initial moves, no player is allowed to repeat what their opponent did last move. In a second part, I will adress the reading that "the move must be different from the last move played by them" means that apart from both player's initial moves, no player is allowed to repeat what they themselves did last move. Finally, in a third part, I will adress the case where both of these apply.

Part I: no last-move copycat

Spoiler: Alice wins for $d\in \{2,3\}$, Bob wins for $d\in \{1,4,5,...\}.$

1. Implication of rules The qoq "best" way to think about this specific game is to understand the power of position, i.e. being the person to not act first, paired with the power of moving $0$, which Bob can always do turn 1, and Alice can never repeat as per rules. This is enough to deduce that Alice must win on turn 1, which is possible iff $d=2$ or $d=3$.

For all other values of $d$, Bob wins. Let's have a look at a few of them.

2. Discussion of first few cases
For $d=1$, Alice either overshoots with an initial $A2$ and $A3$, or prolongs her game by opening $A0$, when Bob in turn elects the play the sequence $\{A0-B0-AX\}$, forcing Alice to overshoot. (Note that from a strategical point of view, all of Alice's opening moves are optimal, as they all loose by force; practically however, $A0$ is preferable since it allows Bob to play suboptimally.)

For $d=4$, we have
$\{A3-B0-AX\},$ where Alice overshoots, or
$\{A2-B2\}$, where Bob lands, or
$\{A0-B2-A0-B2\}$ and $\{A0-B2-AX\}$. Bob wins.

For $d=5$, we have what you described, $\{A0-B0-A2-B3\}$ or $\{A0-B0-A3-B2\}.$

For $d\gt5$, the recurring scheme is that Bob can force Alice into a line described above.

F.e. for $d=6$, we have the simple $\{A3-B3\}$ for opener $A3$, $\{A2-B2-AX\}$ or $\{A2-B2-A0-B2\}$ for opener $A2$, and for opener $A0$ we have $\{A0-B3-A2-B0-AX\}$ or $\{A0-B3-A0-B3\}$. Bob wins.

For $d=7$, we either have prefix $\{A0-B0-A2-B0-\}$ and now $d=5$, with Alice to act and no $0$-move at hand, or we have prefix $\{A0-B0-A3-B0-\}$ and now $d=4$, again with Alice to act and no $A0$-move at hand. Alice may thus not open with $A0$. But opening with $A2$ brings herself directly into $d=5$, which is a win for Bob, since he can play $B0$, and opening $A3$ brings herself into $d=4$, which we saw earlier is also a win for Bob.

For $d=8$, which should be the last case of interest, since it's Alice's $d=3(+5)$, we have straight away that both $A3$ and $A2$ lead to $d=5$ and $d=6$ respectively, where Bob has a win as seen before. Again however, Alice cannot force Bob into such lines with roles reversed with $A0$, since Bob can answer with $B0$, effectively re-reversing roles.

3. Conclusion Alice can thus never force Bob into "her" two winning cases $d=2$ and $d=3$, because Bob can prevent this by playing $B0$. In fact, Bob can continuously play $B0$ and let Alice close the distance with $A2$ and $A3$ until $4\le d\le 6$ when Bob either snaps the win or forces Alice to overshoot as seen above. This is in line with the observation that Alice must win with her initial move, otherwise Bob has a win. So in short, Bob in last position can always move when they are in a Bob's endgame line and always pass otherwise, effectively revearsing roles, or strategy-stealing.

Part II: no second-to-last-move copycat

Spoiler: Alice wins for $d\in \{2,3,4\}$ and in $(d\equiv 4\mod5).$ Bob wins for $d\in \{1,5,6,7,8,10...\}.$

This game is what the author(s) must have had in mind, since $d=94$ is indeed a win for Alice. Interestingly, it comes with a new strategic option for Bob, which is to reduce to $d\in \{2,3\}$ when Alice is prevented from finishing due to her last move having been what is required. This allows Bob to steer into wins when $(d\equiv 2 \mod5, d\gt5)$. Notably for $(d\equiv 3,4\mod 5)$ however, Alice wins.

1. Discussion of first few cases

For $d=1$, we have again $\{A0-B0-AX\}$, and Bob wins.

For $d \in \{2,3\}$, Alice wins turn $1$.

For $d=4$, Alice wins with $\{A3-B0-A0-BX\}$ where she forces Bob into overshooting.

For $d=5$, again no changes, still $\{A0-B0-A3-B2\}$ and $\{A0-B0-A2-B3\}$ for a win for Bob.

For $d=6$, we have the trivial $\{A3-B3\}$, so Alice can't open $A3$. For $A2$, we have $\{A2-B3-A0-B0-AX\}$ where Bob brings $d$ down to $1$ and forces Alice to overshoot. For $A0$ lastly, Bob repeats with $B0$, denying the revearsing of roles and forcing Alice to open into $d \in \{3,4\}$. Note that Bob didn't play $B0$ turn $2$ before, which validates the prefix $\{A0-B0-...\}$.

For $d=7$, we have $\{A3-B3-A0-B0-AX\}$ where Bob reduces to $d=1$, and $\{A2-B3-A0-B2\}$, where Bob reduces to $d=2$ at a time when Alice can't close the game with $A2$, as this was her last move. This is the above-mentioned strategical play for Bob in position, and it highlights the power of position. For the $A0$ opening, note again that Bob is safe playing $B0$, since his follow-up do not need him to play a second turn $B0$ again, validating the prefix $\{A0-B0-...\}$. So $\{A0-B0-A2-B3-A0-B2\}$ and $\{A0-B0-A3-B3-A0-B0-AX\}.$

For $d=8$, Alice wins with $A2$, reducing to $d=6$ while holding the option of $A0$ next turn. Against $A2$, if Bob plays $B2$ and reduces to $d=4$, Alice can force Bob to overshoot in sequence $\{A2-B2-A3-B0-A0-BX\}.$ Against Bob's $B3$, Alice wins immediately with $\{A2-B3-A3\}.$ Lastly, should Bob reply with $B0$, Alice is now in position to re-revearse with $\{A2-B0-A0-B2-A3-B0-A0-BX\}$ or $\{A2-B0-A0-B3-A3\}.$ So, Alice wins for $d=8$ and for all $(d\equiv 3\mod5,d \gt5)$
For $d=9$ and in fact all $(d\equiv 4\mod 5)$, Alice wins.

2. Conclusion
The interpretation that the players may not repeat their own last move, i.e. the second to last move overall, helps Bob in position, in that it opens Bob up to reduce to $d \in \{2,3\}$ exactly when Alice is forced by the rules to play a move different from what's required to land on Bob's spot. However, Alice wins for initial $(d\equiv 3,4\mod 5)$, as well as initial $d \in \{2,3\}$ where Alice wins turn $1$.

This result is in line with your assumption.

Part III: neither second-to-last-move nor last move copycat

Spoiler: Alice wins for $d\in\{2,3\}$ and for $(d\equiv 1,2 \mod 5, d\gt5)$.

It should be clear that the game is the same as the first one for $d \in \{1,2,3,4,5\}$. So, what about $d\gt5$?

For $d=6$, trivial is $\{A3-B3\}$. Against $A2$ however, Bob loses by force with all his replies, $\{A2-B3-A0-B2\},\{A2-B2-A0-B3\},\{A2-B0-A3-B2\}.$
This now highlights that starting with Bob's first move, we have repeating $3$-cycles, reducing to $d-5$ over three plies. Alice wins games where $(d \equiv 1 \mod 5, d \ge 2).$

For $d=7$, we have the same when Alice reduces to $d=4$ again, now with $A3$. We have $\{A3-B3-A0-B2\}$ and Bob overshoots, $\{A3-B2-A0-B3\}$ also overshooting, $\{A3-B0-A2-B3\}$ again overshooting. Alice wins games where $(d \equiv 2 \mod 5, d \ge 5).$

For $d=8$, Bob wins by completing to $5$ in $\{A3-B2-A0-B3\}$ and in $\{A2-B3-A0-B2-A3\}$ where Alice overshoots. Alice also loses with an initial $A0$ on the base of prefix $\{A0-B0-...\}$. Bob wins games where $(d \equiv 3 \mod 5, d \ge 5).$

For $d=9$, Bob wins with $\{A3-B3-A2-B0-AX\}$ and $\{A3-B3-A0-B2-AX\}$ against $A3$, and against $A2$ with $\{A2-B3-A0-B2-AX\}.$ The prefix case $\{A0-B0\}$ splits into the trivial tail against $A2$ with $\{A0-B0-A2-B3-A0-B2-AX\}$ and into the restricted case of $\{A0-B0-A3-B2-A0-B3-AX\}$ where Bob could not play $B3$ turn $2$ as opposed to above, but still wins. Bob wins games where $(d \equiv 4 \mod 5, d \ge 5).$

Bob also wins games where $d \equiv 0 \mod 5, d \ge 2$, since he can simply complete to $5$ or play our double pass-prefix.

2. Conclusion Since the game turns into cycles from turn $2$, Bob can no more prevent Alice from revearsing roles; instead, Alice now has options to steer the game into favourable endgames. That is, Alice wins for $d\in\{2,3\}$ and for $(d\equiv 1,2 \mod 5, d\gt5)$, Bob wins the rest.

Related Solutions

[Math] Alice and Bob Game

The complete solution to this game is harder than it looks, due to complications when there are several numbers $1$ present; I claim the following is a complete list of the "Bob" games, those that can be won by the second player to move. To justify, I will indicate for each case a strategy for Bob, countering any move by Alice by another move leading to a simpler "Bob" game.

I will write game position as partitions, weakly decreasing sequences of nonnegative integers (order clearly does not matter for the game). Entries present a number of times are indicated by exponents in parentheses, so $(3,1^{(4)})$ designates $(3,1,1,1,1)$. Moves are of type "decrease" (type 1 in the question) or "merge" (type 2); a decrease from $1$ to $0$ will be called a removal.

Bob-games are:

$(0)$ and $(2)$
$(a_1,\ldots,a_n,1^{(2k)})$ where $k\geq0$, $n\geq1$, $a_n\geq2$, $(a_1,\ldots,a_n)\neq(2)$, and $a_1+\cdots+a_n+n-1$ is even. Strategy: counter a removal of one of the numbers $1$ by another such removal; a merge of a $1$ and an $a_i$ by another merge of a $1$ into $a_i$; a merge of two entries $1$ by a merge of the resulting $2$ into one of the $a_i$; a decrease of an $a_i$ from $2$ to $1$ by a merge of the resulting $1$ into another $a_j$; any other decrease of an $a_i$ or a merge of an $a_i$ and $a_j$ by the merge of two entries $1$ if possible ($k\geq1$) or else merge an $a_i$ and $a_j$ if possible ($n\geq2$), or else decrease the unique remaining number making it even.
(to be continued...)

Note that the minimal possibilities for $(a_1,\ldots,a_n)$ here are $(4)$, $(3,2)$, and $(2,2,2)$. Anything that can be moved into a Bob-game is an Alice-game; this applies to any $(a_1,\ldots,a_n,1^{(2k+1)})$ where $k\geq0$, $n\geq1$, $a_n\geq2$, $(a_1,\ldots,a_n)\neq(2)$ (either remove or merge a $1$ so as to leave $a_1+\cdots+a_n+n-1$ even), and to any $(a_1,\ldots,a_n,1^{(2k)})$ where $k\geq0$, $n\geq1$, $a_n\geq2$, and $a_1+\cdots+a_n+n-1$ odd (either merge two of the $a_i$ or two entries $1$, or if there was just an odd singleton, decrease it). All cases $(3,1^{(l)})$ and $(2,2,1^{(l)})$ are covered by this, in a manner depending on the parity of $l$. It remains to classify the configurations $(2,1^{(l)})$ and $(1^{(l)})$. Moving outside this remaining collection always gives some Alice-game $(3,1^{(l)})$ or $(2,2,1^{(l)})$, which are losing moves that can be ignored. Then we complete our list of Bob-games with:

$(1^{(3k)})$ and $(2,1^{(3k)})$ with $k>0$. Bob wins game $(1,1,1)$ by moving to $(2)$ in all cases. Similarly he wins other games $(1^{(3k)})$ by moving to $(2,1^{(3k-3)})$ in all cases. Finally Bob wins $(2,1^{(3k)})$ by moving to $(1^{(3k)})$ (unless Alice merges, but this also loses as we already saw).

[Math] Alice and Bob number sum game

There is really only one "move" in the game. Alice needs to decide who should go first. After that, both players are playing mechanically.

To decide who goes first, Alice finds the least X such that no subset of the available numbers adds up to X. Play will end on turn X, and Alice wants to be the one whose turn that is. So, if X is odd, Alice plays first; otherwise she lets Bob play first.

To easily determine X, Alice uses a Sieve. You're probably familiar with the Sieve of Eratosthenes, used to find primes. Same idea, but with different rules for a different purpose.

Alice writes down the numbers from 0 to the sum of all the numbers on the table, and crosses off 0. Then she takes numbers from the table, one at a time, without replacement. When she takes off the number Y, she crosses off every number that is Y plus some previously-crossed off number. When she has done this for every number on the table, the smallest un-crossed-off number is X.

Notice that this works even if the numbers on the table are not all distinct.

It even works if some of them are negative or zero, except that then Alice's initial list runs from the sum of the negative numbers thru the sum of the positive numbers, and X is the least positive un-crossed-off number.

Improved solution

Assume the numbers on the table are distinct positive integers.

If there were no missing numbers, any sum up to $S(N) = N(N+1)/2$ could easily be gotten, and X would be $S(N) = 1$.

But there are missing numbers. Let's start with an empty table, add numbers to it in increasing order, and after placing each number $n$ compute $S(n)$ = sum of all numbers on the table up to $n$. The question is, is it still true that a player could get any sum up to $S(n)$ from these numbers, assuming it was true for $S(n-1)$ before placing $n$.

Well, if $n \le S(n-1)+1$, then the answer is clearly yes. You could already get any sum up to $S(n-1)$ without using $n$. To get a sum $s$ where $S(n-1) \lt s \le S(n)$, combine $n$ with a combination summing to $s - n$ from the smaller numbers.

Conversely, if $n \gt S(n-1)+1$, then the answer is no. The sum $S(n-1)+1$ is unachievable without using $n$, because it exceeds the sum of the other numbers, and is also unachievable using $n$, because $n$ by itself is already too large.

And that leads to an obvious $O(N)$ algorithm to find X

X = 1
for n from 1 to N
    break if n > X
    X += n unless n is one of the missing numbers
end
return X

(I assume it's obvious how to do unless n is one of the missing numbers in constant time, assuming they are given to us in ascending order.)

But if $K$ is much smaller than $N$ we can do better. Suppose we're given the missing numbers in ascending order. Then

MSUM = 0
for each missing number m
    MSUM += m
    X = m * (m + 1)/2 - MSUM + 1
    return X if m >= X
end
return N * (N + 1)/2 - MSUM + 1

This runs in time $O(K)$.