0
$\begingroup$

Find a winning or a non-losing strategy for the following game: Consider $25$ sticks arranged in a $5$ x $5$ square. Players alternately take any number of sticks from a single row or column. At least one stick must be taken. There is an additional restriction that a group of sticks cannot be taken if the group contains a gap. The last person to move wins.

My strategy:

I was thinking that $A$ (first player) has a winning strategy if he goes first over $B$ (second player). I was thinking what if $A$ leaves $B$ with jan odd number of sticks. Wouldn't that be a setup for a win for $A$?

Can I get help with providing a logical argument on who has the winning strategy or non-losing strategy in this game? My friend and I were having a discussion about this problem after we saw this problem in E. Mendelson "Introducing Game Theory and its Applications". I said $A$ has a winning strategy but he said $B$ might have win therefore it is a non-losing strategy.

Can someone help me to prove this problem highlighted above with a convincing logical argument?

$\endgroup$
5
$\begingroup$

Your answer is not quite right. For example, if A leaves just 1 stick B will win; but if A leaves to sticks touching horizontally or vertically, B will still win.

The game as stated as an easy solution: A takes, on his first move, all of the middle column. Then whenever B moves on one side, A mimics that move on the other side. Since they are disconnected, A can always get the last move this way.

In combinatoric game theory language, the set of 2 disjoint positions A leaves are equivalent, therefore they have the same nimber (or Grundy function) therefore the nim sum of the two is zero, thus a win for the player (A) who left that position.

The first player has a win in this way if either the number of rows or columns is odd.

The game is less trivial for an $N \times M$ rectangle with $N$ and $M$ both even, since that symmetry strategy is unavailable. That is a win for the second player, via a different symmetry strategy.

$\endgroup$
  • $\begingroup$ In the rectangle case (both N and M are even), the 'different' symmetry strategy resulting in the win for the 2nd player: keeping the centre of the board as the 'symmetry point' work? (by symmetry about the point, I mean the kind of symmetry an odd function has about origin) $\endgroup$ – talegari Jun 11 '14 at 7:40
  • 1
    $\begingroup$ For N and N even, consider a fictitious point C at ((M+N)/2,(M+N)/2). For each point P taken by A in a move, B takes the point which is the same distance from C, and on the the line PC (a reflection about point C). It is easy to see that (1) A can never take a point and its reflected image; (2) if A's move of some set of such points is legal, then so is B's reply; (3) if some set of points is available for A to take, its image is available for B. So this is a winning strategy, as B always has a reply to A's move. $\endgroup$ – Mark Fischler Jun 12 '14 at 19:44
  • $\begingroup$ Thanks, that what I thought. $\endgroup$ – talegari Jun 13 '14 at 7:13

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.