1
$\begingroup$

Andy and Bob play a game using a long straight row of squares, alternating turns. When it’s Andy’s turn, he writes an A in one of the blank squares. When Bob takes a turn, he writes a B in some blank square. (Once a letter is written in a square, neither player can use that square again.) A player wins the game when his initial is written in 4 equally-spaced squares. For example, suppose the following board is the result of several turns: (below)

     _ _ B B _ A B A _ _ _ A B _ _ A                        ^                        | 

Andy can win by writing A in the indicated square. (Four A’s with spacing 2) Bob can win by writing B in that same square. (Four B’s with spacing 3)

  • If Andy goes first, find a strategy Andy can use that guarantees that he wins. How many moves must Andy make to get 4 in a row, no matter what moves Bob makes? (Can Andy always win in just 4 moves?) Justify your answer.
  • How many squares are needed in the game board to allow Andy’s strategy to work?
  • 1
    @Blue Eyes, if you want to ask another question, use "ask question" on top; do not edit this question.2012-04-20

1 Answers 1

7

Andy wins in 4 moves. Denote Andy's first move as position $0$. Without loss of generality, Bob places his move at $n$, then Andy plays at $2(n+1)$. If Bob does not play at $n+1$, $-(n+1)$ or $3(n+1)$, Andy plays at $n+1$ and wins in the next move by either playing at $-(n+1)$ or $3(n+1)$. If Bob did play one of the mentioned moves, then Andy wins by playing at $4(n+1)$ followed by either $6(n+1)$ or $-2(n+1)$.

Minimal board size looks slightly more annoying to figure out at first glance; considering that Andy's second move could happen at the opposite side of Bob's first, it looks like Bob can only prevent a spacing of $1$ and $2$, so that would mean a board size of $21$ would suffice, but I don't see a quick way to prove that without looking at several different cases, and it's entirely possible I overlooked something with that.

  • 0
    I think that with 25 board you can guarantee a win in 4 moves, and under it is not possible (but maybe you can win with more moves). If A play in x, and B in x+2, A should play his next move in x+6 or x-6, so at least 6*4+1 space are requested.2012-04-19