I'm hoping someone can help me figure out how to describe all winning strategies for "Player 1" in the following game:

Consider a board with $n$ tiles arranged in a row. Player 1 and Player 2 each have $d$ turns, and Player 1 always goes first. On the first turn, Player 1 "issues an order," or in other words, gives a number between $0$ and $n-1,$ and Player 2 chooses a tile on the board to place his piece and then moves either left or right according to the order given by Player 1. Player 2 is never allowed to change direction mid-move. In each subsequent turn, Player 1 issues another order (again, always a number between $0$ and $n-1$), and Player 2 must attempt to execute the order by moving left or right from the square he finished on during the previous turn. Player 2 wins the game if he is able to follow each order and last until the $d$ turns are over, while Player 1 wins if he is able to issue an order that Player 2 cannot follow.

Certainly, if $d=1$ or $d=2$ there are no winning strategies for Player 1, while for $d \geq 3$ there are. So my question is, what are they? Or, put it another way, how can we be sure that a sequence of $d$ orders issued by Player 1 will not be able to be followed by Player 2?

EDIT: Thanks to all for your comments and/or criticism. I probably should have included this in my initial post (sorry, first time poster mistake), but this game is related to another problem I was interested in solving:

Which sequences of $d$ integers $e_1, e_2, \dots, e_d,$ with $0 \leq e_i \leq n-1,$ create a system of equations $e_i = |x_i - x_{i+1}|,$ $i=1,2, \dots, n,$ which admits at least one solution in $x_1, x_2, x_3, \dots, x_{d+1},$ with $0 \leq x_i \leq n-1?$ The losing strategies for Player 1 in the above game would yield such sequences, for as Player 2 executes the "orders" given by Player 1 (which would form a sequence $\{e_i\}_{i=1}^d$), he generates a solution (in $x_j$) to the above system of equations.


Maybe I'm missing something, but it seems that if player 2 lands away from one of the extremal tiles in less than $d$ turns, (s)he has lost (since, then player 1 can order player 2 to move n-1 places).

So wouldn't the winning strategy (for $n>2$ and $d>2$) be $n-1$, $1$, $n-1$?

Edit: Steven Stadnicki points out that even when player 1 cannot use the same order twice, there is still a winning strategy: $n-1, 2, n-2$. This works if $n>4$. For $n=4$, player 1 should first order 0. If player 2 puts his piece on the edge, then $1,3$ wins, and if player 2 puts his piece off the edge, then 3 wins.

  • $\begingroup$ Note that restricting player 1 to a permutation of $0\ldots n-1$ doesn't work either; they can just choose $n-1$ (forcing player 2 to go to the edge of the board), $3$, $n-2$. $\endgroup$ – Steven Stadnicki Sep 17 '13 at 20:54

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.