# Winning or Non-losing strategy for A or B

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?

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.

• 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) – talegari Jun 11 '14 at 7:40
• 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. – Mark Fischler Jun 12 '14 at 19:44
• Thanks, that what I thought. – talegari Jun 13 '14 at 7:13