27
$\begingroup$

Alice and Bob and the referee Conny play the following game with a pawn on a standard $8\times8$ chessboard:

  • In the beginning, Conny places the pawn into the center of a randomly chosen square. All $64$ squares are chosen with equal probabilities.
  • Then Alice and Bob alternate turns; Alice starts.
  • In every turn, the pawn is moved to a new square. The pawn is always placed into the very center of a square.
  • The (Euclidean straight line) distance moved by the pawn must be strictly larger than the (Euclidean straight line) distance moved by the pawn in any of the preceding moves.
  • A player unable to move loses the game.

Question: What is the probability that Alice wins this game? (As usual, we assume that Alice and Bob both use optimal strategies.)

$\endgroup$
33
$\begingroup$

Alice wins with 100% probability.

Strategy:

On each of her turns Alice will place the pawn onto the square which is exactly opposite of the original square over the center of the board.
Now Bob will have to move the pawn further than Alice did and will involuntarily end up being closer to a corner than Alice was before.
With every turn Alice will not change the minimum distance to one of the corners while Bob will get closer and closer.

How this works:

Lets look at it from the end of the game:
The person who jumps from one corner of the board to the opposite corner (for example A1 to H8) will win, because the opponent can't make a longer jump than that.
The person who jumps into a corner first will lose, because the opponent can jump into the opposite corner afterwards.
The only way to force your opponentinto the corner is if you jumped from a square directly next to a corner to the opposite square (for example A2 to H7).
Therefore the first person to jump onto a square directly next to a corner will lose because the opponent can from there on out force the moves.
And so on and so forth.

$\endgroup$
  • 3
    $\begingroup$ I think you're right, but your expression of the solution is not clear at all and relies on the reader to fill in a lot of details and resolve ambiguities like what the "original square" means. $\endgroup$ – R.. Nov 23 '15 at 16:55
9
$\begingroup$

Alice always wins. If Alice is at $p$, her winning strategy is to hop to $p'$, such that the midpoint of $p$ and $p'$ is the center of the board.

We need only prove that this move is always legal for Alice to make. Since she never is without a legal move, she wins.

She can certainly do this on her first move. Suppose Alice has just hopped from $p$ to its opposite, $p'$, and then Bob hopped from $p'$ to $q$. Let $q'$ be the opposite of $q$, and let $o$ be the center of the board. Finally, let $d(a,b)$ mean the distance between points $a$ and $b$, and recall the triangle inequality $d(a,c)\le d(a,b)+d(b,c)$, for any $a,b,c$.

First, we show that $d(q,o)>d(p',o)$. Supposing not, it would follow that $$d(p',q)\le d(p',o)+d(o,q)\le d(p',o)+d(o,p')=d(p',p),$$ but $d(p',q)\le d(p',p)$ contradicts the fact that it was legal for Bob to hop from $p'$ to $q$.

With this fact under our belts, we know have that $$d(p',q)\le d(p',o)+d(q,o)<d(q,o)+d(q,o)=d(q,q')$$ This proves that it is legal for Alice to hop from $q$ to $q'$.

$\endgroup$
6
$\begingroup$

For an $m\times n$ board.

If $m$ or $n$ is even:

Alice can win with 100% probability using @TheDarkTruth's strategy.

If both $m$ and $n$ are odd:

Given an optimal strategy from both players, Alice will win with 100% probability all games where she start off-centre and lose with 100% probability the games where she starts in the centre of the board; so her overall probability is $\frac{mn-1}{mn}$.

Explanation:

In the case of starting in the exact centre of the board, Alice initially moves the pawn out of the centre then Bob can then follow @TheDarkTruth's strategy with the roles reversed). An $8 \times 8$ board always gives the first player a 100% probability of winning as the pawn will always start off-centre.

$\endgroup$
  • $\begingroup$ There is no centre of an 8x8 board. $\endgroup$ – Trenin Nov 24 '15 at 14:59
  • $\begingroup$ Yes - I noted that in the explanation section. This was expanding the question to the general case of a MxN board rather than just an 8x8 board. $\endgroup$ – MT0 Nov 24 '15 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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