10
$\begingroup$

Alice and Bob play a game on the following irregular chessboard. (Note the blacked out squares are not legal moves.)

The game board.

  • Alice starts the game by placing a knight on any square she chooses.
  • They then take turns, starting with Bob, moving the knight as a knight moves in chess.
  • Immediately reversing the previous move is not allowed. That is, if one player moves the knight from square $x$ to square $y$, the next player is not allowed to move to square $x$ during the immediate next turn.
  • The winner is the first player to move to a square that has been previously occupied sometime during the game.

Who wins with optimum play and why?

Improve this question
$\endgroup$
8
  • $\begingroup$ Do we need to provide a winning strategy or is a proof enough? $\endgroup$
    – VicAche
    Dec 12, 2015 at 12:08
  • $\begingroup$ I'm expecting a proof without any specific winning strategy. $\endgroup$
    – Tyler Seacrest
    Dec 12, 2015 at 17:20
  • $\begingroup$ So I guess proving that a) no draw is possible and b) every possible winning strategy for Bob can be mimicked by Alice (or Alice by Bob) would do? $\endgroup$
    – VicAche
    Dec 12, 2015 at 17:25
  • $\begingroup$ @VicAche I think the "strategy stealing" argument won't work here, for the same reason as in this question. $\endgroup$
    – Sleafar
    Dec 12, 2015 at 18:10
  • $\begingroup$ @Sleafar the problem might apply but it may still be easier using that than through brute-force. $\endgroup$
    – VicAche
    Dec 13, 2015 at 10:19

1 Answer 1

Reset to default
4
$\begingroup$

Alice wins.

Suppose for contradiction that Bob has a winning strategy.

Claim: If Alice makes the first move on square X, then on the next turn (Bob's), there is exactly one square Y among the neighbors of X on which Bob must make his (first) move to win.

Assuming the claim, for each square X, let f(X) denote the Y as in the claim. Then since there are more W squares than B, there must be two W squares $X_1,X_2$ and a B square Y such that $f(X_1)=f(X_2)=Y$.

Now this gives a strategy for Alice to win by starting at $Y$: if Bob places the knight on a square other than $X_1$, Alice steals Bob's strategy by pretending that Bob already made a move at $X_1$; if Bob places the knight on $X_1$, Alice pretends that the first move was Bob's at $X_2$ and again wins by strategy-stealing.

Proof of the claim:

Suppose for contradiction that Y, Z are two squares both adjacent to X and such that when Alice starts at X, then Bob has a winning strategy by placing his knight at Y or at Z.

Let Alice begin a game by placing the knight at Y. Now if Bob doesn't place the knight at X, then Alice can pretend to be the second-player where the game began with Bob starting at X; this is a contradiction so Bob must place the knight at X.

But in this case Alice can place the knight on Z and by strategy-stealing again, go on to win. This proves the claim.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ In regards to the proof of claim, what if the winning strategies through Y and Z both end (or can be made to end) with a winning move back to X? Strategy-stealing would just end up with Alice moving to X and Bob winning on Y/Z. $\endgroup$
    – Zandar
    Dec 13, 2015 at 18:26
  • $\begingroup$ @Zandar, I don't understand. Since Y and Z are winning for Bob, how can the winning move finish at X? $\endgroup$
    – Aravind
    Dec 13, 2015 at 18:34
  • $\begingroup$ I mean the winning move in Bob's original strategy where Alice starts at X. If that winning move is back to X, then it no longer applies if Alice starts at Y or Z instead. $\endgroup$
    – Zandar
    Dec 13, 2015 at 18:40
  • $\begingroup$ This is very close! What I don't understand is, just before you start to prove the claim: It's true that if Alice starts on $X_2$ that Bob needs to move to $Y$. You say if the game starts $X_1, Y, X_2$ that Bob would need to move to $Y$ to win. But now the board is changed so that $Y$ has already been visited, maybe this opens another winning option for Bob? $\endgroup$
    – Tyler Seacrest
    Dec 14, 2015 at 16:02
  • $\begingroup$ @Zandar: I think the proof of the claim is okay. Imagine the board is colored like a chessboard with alternating black and white squares. If Alice starts at X and Bob ends up winning, then the winning move can't be X because (say) X is a black square, and whenever Bob moves he moves to white squares. $\endgroup$
    – Tyler Seacrest
    Dec 14, 2015 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.