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?
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.