1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help finding winning strategies in the following tile game?

  1. Oct 23, 2013 #1
    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?


    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.
  2. jcsd
  3. Oct 25, 2013 #2
    I do understand the game from your description (at least 90%). However, I don't quite understand the question you are asking so I am just sharing my view on the game here.

    Let's say after first turn, the piece is not at the edge of the board, Player 1 will certainly win by issuing an order of n-1. Thus, the only way for Player 2 to survive 2nd turn is to move the piece to the edge of the board during 1st turn.

    With the above understanding, it is easy to see that Player 2, upon hearing the number given by player1, will always place the piece somewhere in the board such that the piece can be moved to the edge of the board after the order is executed.

    In the beginning of the 2nd turn, the piece is at the edge. Now, Player 1 can issue an order of any number, say r. Player 2 will then move the piece accordingly. During the 3rd turn, Player 1 can then issue an order of n-r to win because the total number of movements of the last 2 turns is r + (n-r) = n, which is greater than n - 1.
  4. Oct 25, 2013 #3


    User Avatar
    Science Advisor

    Putting that together, player 1's supposed winning strategy would be ( n-1, r, n-r )
    But if r > n/2 then player 2's compliant implementation could be ( 1, n, n-r, 2n-2r )

    I think that jjuren has already worked this much out. He is after constraints like "r > n/2" but with considerably more generality.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Help finding winning strategies in the following tile game?