Removing pawns - the game

[witzar]

Here is the simple game I've invented (if someone invented it before, then I'm not aware of it):

 

A pawn is placed on every square of m*n chessboard.
Two players take alternate turns removing pawns.
On each turn, a player removes one or more pawns.
All pawns removed in a single turn have to be taken from the same row or the same column.
The player who cannot make a move loses (alternatively: the player who takes the last pawn wins).

Let's call the player who begins the "first player" and the other one the "second player".

Which player (the first or the second) has a winning strategy depending on the chessboard dimensions?
 

PS The game can be played on more interesting boards. Just draw some number of crossing lines

on a sheet of paper and place a pawn on each point of intersection of the lines.

The pawns removed in a single turn should come from a single line.

I've tried to play this game on the pentagram (the star: five lines, ten points/pawns) with my 9 years old daughter.

It was fun. Determining which player wins was even bigger fun.

[DejMar]

Sorry to report, but you are not the inventor of the game. The game is known as Nim. There are many variants to the game. In yours, you have simply (if I may use that term here) replaced the "stones" with pawns, and a "heap" with a row or column. A theorem states, for a normal game of Nim, such as "Removing pawns", that the player making the first move has a winning strategy if the nim-sum of the size of the "heaps" is non-zero, otherwise, the second player has a winning strategy. A difference between "Removing pawns" and the traditional game

is that there are two sets of "heaps": rows and columns.

What question arises is, with both rows and columns to consider, is the nim-sum computed for both rows and columns?

[witzar]

@DejMar

Of course I know the game Nim. That's a classic.

My game is quite similar, but still different.

Nim has beautiful analysis of the winning strategy,

and the strategy turns out to be very simple.

But neither the analysis of Nim nor the strategy applies to my game.

[DejMar]

I don't have a proof, but I am not so sure that the basic analysis would not apply. Nonetheless,

Player 1 has the winning strategy.

Player 2 has the winning strategy.

[witzar]

Player 2 has the winning strategy.

This is incorrect (for example m=2, n=1).

[Brainy Binary]

The first or second player have overall advantage if all possible

mxn board will be considered?

[DejMar]

 

Player 2 has the winning strategy.

This is incorrect (for example m=2, n=1).

 

Yes, witzar, I should have added for the condition m=2, such that n > 1.

[gavinksong]

I don't have a proof, but I am not so sure that the basic analysis would not apply. Nonetheless,

Player 1 has the winning strategy.

Player 2 has the winning strategy.

This is true for all m and n > 1?

For n>1, wouldn't Player 1 have the winning strategy for m=3, since he could easily remove a line and reduce the game to m=2?

[DejMar]

 

I don't have a proof, but I am not so sure that the basic analysis would not apply. Nonetheless,

Player 1 has the winning strategy.

Player 2 has the winning strategy.

This is true for all m and n > 1?

For n>1, wouldn't Player 1 have the winning strategy for m=3, since he could easily remove a line and reduce the game to m=2?

 

...but if the first player removed a line, reducing the game to m=2 (n>1), it would not be a winning strategy. Player 1 would not be the "first player" to make a play at/after the point the game became m=2, (n>1). Of course, this may not be true if a number of pawns had been removed from other lines during the process. The answer I gave is based upon rows and columns where the value of m and the value of n are the same for each.

Though the calculation of a nim-sum may not be formulated for this variation of the game, I believe such a formula may exist and be able to identify the player with the winning strategy.

 

Edited October 26, 2014 by DejMar

[witzar]

Yes, witzar, I should have added for the condition m=2, such that n > 1.

This is incorrect.

[gavinksong]

Yes, witzar, I should have added for the condition m=2, such that n > 1.

This is incorrect.

DejMar,

Here's a small proof by contradiction. What I said earlier is correct. If what you said is true, then for m=3, the first player can just remove a line reducing the game to m=2 where he is the second player. Since you said that the second player is guaranteed to win in m=2, the first player to move in m=3 would win the game. However, (since n and m are exchangable) this implies that the first player wins for all n=3, which contradicts what your claim that the second player wins for all cases of m=2. Thus, this claim must be false.

[bonanova]

I find witzar's game innovative and interesting.

 

The fact that each pawn belongs both to a row and to a column distinguishes it from nim, where nim sums (of a one-dimensional array of heaps) are amenable to establishment and maintenance. By contrast, in this game, while row sums or column sums might be managed by a player, they cannot both be managed. This follows from the fact that when multiple pawns are removed from a column, for example, no more than one pawn can be removed from rows, and vice-versa, preventing control of both dimensions. Another difference is that while one player on his turn may attempt to manage rows, his opponent may counter by choosing to manage columns.

[DejMar]

Okay. Again, I was incorrect. Partly due to an incomplete definition of the relationship of m and n.
For any solution for m,x the same solution would apply for x,n. Thus, for a specific case m = x, the case is for n = m = x. 
For such, the player identified in the partial solution where m=2 should be correct.

 

I am not adept a formulating proofs, so I will not try here.

Testing for m,n : m=2, 1 <= n <= 6, it appears that when n=odd the "first player" has the winning strategy, n=even the "second player" has the winning strategy. Intuitively, this should be able to be extended for all positive integers of n.

[Barcallica]

If at least one of m or n is odd, player 1 wins. First he removes middle line, then do actions symmetrical to player 2's actions with the removed line.

if m and n both even, player 2 wins. Every move player 1 make, player 2 make symmetrical move with center point.  

[witzar]

If at least one of m or n is odd, player 1 wins. First he removes middle line, then do actions symmetrical to player 2's actions with the removed line.

This is incorrect.

Consider 3*3 for example. After player 1 removes middle line, player 2 removes some line perpendicular to line just removed, leaving player 1 with 2*2.

 

if m and n both even, player 2 wins. Every move player 1 make, player 2 make symmetrical move with center point.

This is correct.

[Barcallica]

 

If at least one of m or n is odd, player 1 wins. First he removes middle line, then do actions symmetrical to player 2's actions with the removed line.

This is incorrect.

Consider 3*3 for example. After player 1 removes middle line, player 2 removes some line perpendicular to line just removed, leaving player 1 with 2*2.

 

if m and n both even, player 2 wins. Every move player 1 make, player 2 make symmetrical move with center point.

This is correct.

 

 

I see. Then strategy would be to make the grid even sided. if m odd and n is even, player 1 can first take one row from m and wins. if both are even he obviously can't take entire row. Maybe take center pawn and do symmetrically?  

Edited October 31, 2014 by Barcallica

[Barcallica]

Let's assume there were only left column and top row. One to remove last pawn is winner because he will be second player of m-1, n-1 both side even board. 

In this new game, 1st player also has the edge. He first takes corner pawn and make it 2 separate line, next he maintains the number of pawns on those lines same.

 

[gavinksong]

Let's assume there were only left column and top row. One to remove last pawn is winner because he will be second player of m-1, n-1 both side even board.

In this new game, 1st player also has the edge. He first takes corner pawn and make it 2 separate line, next he maintains the number of pawns on those lines same.

If the second player removes pawns from either of these lines but also removes pawns from the even board in the same move, there is nothing the first can do about it.

[gavinksong]

I'd like to know the answer