- #1
jjuren
- 1
- 0
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?
It’s not too difficult to come up with particular winning strategies for Player 1, for example if the sequences $n-1, 1, n-1$ or $n-1, 2, n-1$ appeared among the $d$ orders given by Player 1, that would give a winning strategy. More generally a “high-med-high” strategy is always going to do it – Player 2 would, if acting optimally, place his piece on the edges to begin (to allow for the greatest number of possible moves), so a strategy which eventually forces him closer to the middle of the board and then follows up with a high number Player 2 would be unable to comply. The question I’m really asking then is what are the conditions, in terms of $n,$ which characterize these “bad triples.” How low can the first and last numbers in the triple be relative the middle one?
Thanks!
P.S. 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.
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?
It’s not too difficult to come up with particular winning strategies for Player 1, for example if the sequences $n-1, 1, n-1$ or $n-1, 2, n-1$ appeared among the $d$ orders given by Player 1, that would give a winning strategy. More generally a “high-med-high” strategy is always going to do it – Player 2 would, if acting optimally, place his piece on the edges to begin (to allow for the greatest number of possible moves), so a strategy which eventually forces him closer to the middle of the board and then follows up with a high number Player 2 would be unable to comply. The question I’m really asking then is what are the conditions, in terms of $n,$ which characterize these “bad triples.” How low can the first and last numbers in the triple be relative the middle one?
Thanks!
P.S. 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.
