1
$\begingroup$

We have a $25 \times 25$ board and two players.

The fields of the board are numbered like this: From $0$ to $24$ from west to the east, and from $24$ to $0$ from north to the south.

The first player places the pawn in one of the fields in the top line, for example, in the column number $1$. Then the second player moves the pawn in one of three direction by any number of fields: To the south, to the west, or to the south-west, and so does the first player, and so on.

One of the players wins when he places the pawn in the most south-west corner (that is, column $0$, line $0$). Determine the optimal first move for the second player, that is, the move such that after making it the second player will win for sure.

It's a hard problem for me, as I'm not used to dealing with combinatorial game problems. Any hints appreciated.

$\endgroup$
  • $\begingroup$ I believe the same techniques used to show that player 2 has a winning strategy in the game nim will work here (counting path lengths in binary in this case). $\endgroup$ – Justin Benfield Mar 12 '16 at 10:47
  • $\begingroup$ What do you mean by "couting path length in binary"? $\endgroup$ – VanDerWarden Mar 12 '16 at 10:56
  • $\begingroup$ The point of counting in binary in solving nim is that you can force the opponent to be the one who removes the last matchstick (and hence loses) by keeping track of the odd-even parity of the piles of matchsticks. A similar counting strategy is most likely applicable here (except YOU want to be the one making the last move). $\endgroup$ – Justin Benfield Mar 12 '16 at 10:59
  • $\begingroup$ Hetajr, does the pawn only move one space at a time? Are you allowed to write a program? What is the source of this problem and what games/ideas have been covered recently in the class/book? The answer to this is known, but the way you approach it would depend a lot on the relevant context/what you know. $\endgroup$ – Mark S. Mar 12 '16 at 13:57
  • $\begingroup$ I am perfectly allowed to write a program, but I though there is a certain mathematical/combinatorial way to obtain the answer. $\endgroup$ – VanDerWarden Mar 12 '16 at 13:58
3
$\begingroup$

This game does have a number of theorems known about it, but re-deriving tough theory is not necessary for the problem as stated. The key idea for solving a question like this with a program is the concept of winning positions and losing positions (sometimes called $N$-positions and $P$-positions).

For example, $(7,7)$ is a winning position since if the pawn is at $(7,7)$ the next player to move can win by moving the pawn south-west by $7$ units (the OP said "by any number of fields"). More interestingly, $(1,2)$ is a losing position since the next player can only move to $(0,2)$, $(1,1)$, $(1,0)$, or $(0,1)$, all of which are definitely winning positions since the next player from any of them can end the game immediately. Therefore, $(1,3)$ is a winning position since moving to $(1,2)$ would be a good move.

The general definition is that a position is losing if all available moves are to winning positions ($(0,0)$ counts as losing since there are no available moves), and a position is winning if there is at least one move to a losing position. With this recursive definition, you can use a computer program (or pen and paper) to find all of the winning and losing positions among $(a,b)$ for $0\le a,b\le24$. It might be useful to arrange your results in a table or matrix.

It will turn out that the losing positions have a vague pattern, and that all positions of the form $(24,b)$ for $0\le b\le24$ are winning positions, so the "second player" can win no matter which of those positions the "first player" places the pawn. The winning first moves from each position like $(24,b)$ will then be clear from a table of the winning positions and losing positions: just make a move south, west, or south-west that leads to a losing position.

This problem can be done without a computer if you understand how to mark positions in your table by looking at it (it was first solved over 100 years ago), but to do so for larger numbers without the theorems that have been proven would require basically making a big table of winning and losing positions by hand and then seeing a pattern, making a very nonobvious guess at that pattern, then doing a lot of work to prove that pattern. This is why I asked about the context of the problem, because if you had just covered (in the book or class) a theorem which tells you a formula for the winning and losing positions already, then this becomes much easier.

$\endgroup$

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.