0
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\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$ Commented Sep 17, 2013 at 20:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .