Rectangular Nim-Tac-Toe

[BC]

I hope somebody finds this to be an interesting puzzle:

X and Y start with a 3-by-3 grid of squares. X removes a set of squares that comprise a (square or) rectangle. Y follows suit. The one who takes the last remaining piece in the grid is the loser.

What are the possible first moves for X (if any) that will force a win, and what are Y's optimal responses to all other moves?

Note: I considered the normal NIM way of trying to TAKE the last remaining piece, but then I discovered that this was significantly easier to solve (and much less interesting) for at least one first move for X. :wink:

[Hummer]

If I understood the problem correctly, you take the full middle row (either horizontal or vertical).

Now, back to the Poker section. :D

[Colymbosathon ecplecticos]

X can force a win by selecting the middle 1x3 rectangle (2 ways to do this).

[Expunge]

X can force a win by taking a 2 by 2 square.

[4sigma]

X can force a win by taking a 2 by 2 square.
No, I don't think this wins for X. Y responds by taking the opposite corner, leaving two 1X2 rectangles. Now however X responds, Y can force him to take the last square.

[Expunge]

X can force a win by taking a 2 by 2 square.
No, I don't think this wins for X. Y responds by taking the opposite corner, leaving two 1X2 rectangles. Now however X responds, Y can force him to take the last square.

you are correct.

[BC]

So far, so good. But there are other possible winning moves for X, as well.

[Colymbosathon ecplecticos]

Well, that is slightly misleading. There is one more winning move, cute.

[BC]

Are you sure there's only one? I'll recheck my work...

Edited after checking work:

CE is right, I forgot to consider a few cases, and one is where player 2 has a defense to what I thought was a winning first move for player 1. My apologies...

So anyone found the ONLY other first winning move for player 1 (besides CE, presumably) yet?

My mistake was that I THOUGHT taking a single corner square was a winning move for player 1. Somehow I overlooked several defenses by player 2, including the defense of taking a 2-by-2 square that only touched the missing square diagonally, producing 2 1-by-2 rectangles (from which there is no defense remaining for player 1; a pair of 1-by-2 rectangles is one of many no-win positions for the player who receives it.)

[Hummer]

So anyone found the ONLY other first winning move for player 1 (besides CE, presumably) yet?

Boy, it's tough to get credit around here. :viola:

[BC]

...And congratulations to ribeye for finding ONE (or two, if you count the center HORIZONTAL 1-by-3 case seperately from the center VERTICAL 1-by-3 case) of the winning moves for Player 1. How did that get deleted from my prior post, I wonder... must have been a glitch in the internet. That's my story and I'm sticking to it :wink:

[Colymbosathon ecplecticos]

Have you given any thought to the n-dimensional version?

[BC]

No; I haven't even given any thought to the nxn version for n > 3...

Have you?

[Darth Tater]

No; I haven't even given any thought to the nxn version for n > 3...

Have you?

I wonder if n being even or odd makes a difference. Once someone establishes a short proof for the 1x1 and or 2x2 case, it seems as though a general strategy may be employed on an induction basis...such as how to cover a 2nx2n board, one square removed with tri-ominoes.

[Colymbosathon ecplecticos]

I was only considering the 3x3x...x3 (n-times) case. I haven't examined any of these beyond n=2, but I conjecture that there is an N so that for all n>N Player 1 has a win, I have a (very) crude heuristic for this.

[BC]

I'm guessing its along the lines of "take the middle slab and then mirror your opponent until it is no longer in your best interests" or something like that?

Actually, that works for mxn for m,n >= 3 now that I think of it!

If a player is presented with 2 1xn pieces, he is in a losing position because his opponent can mirror him as long as at least 2 pieces have length >= 2. As soon as all except 1 piece goes to length 1 or disappears, take all except an odd number of single squares. Since there is still exactly one piece of length >=2, player 1 can decide the parity by choosing between taking ALL or taking ALL EXCEPT (a single square).

(for example, if 2 1x4s are left and player 2 takes a 1x2 out of the middle, player 1 must take a 1x3 out of the remaining 1x4 to leave 3 single squares).

Okay, we've shown that player 1 has a winning move for mxn, for all shapes in which either m or n is > 3 and the other is > 2.

In the 2x2 case, player 2 has a win (this is easy). In the 1xn case, player 1 can win by grabbing all but a single square. In the 1x1 case, player 1 loses "automatically".

So mxn has been "solved". I guess we have to go to higher dimensions now... you've inspired me :P

[BC]

I was only considering the 3x3x...x3 (n-times) case. I haven't examined any of these beyond n=2, but I conjecture that there is an N so that for all n>N Player 1 has a win, I have a (very) crude heuristic for this.

Furthermore, the above generalizes to m1 x m2 x m3 x .... mN as long as one of the 'm's is greater than 2. In other words, N = 1 for your special case of 3^N.

For the 2^n case, we have an interesting conundrum, however - since 2x2 has no winning position, 2x2x2 DOES - take a slab leaving a 2x2 square. So the last remaining question, I guess, is:

What about 2^n for n>3?

[BC]

Edited to disagree with own "proof".



What about 2^n for n>3?

I think it continues to alternate, that player 1 cannot force a win if n is even, and can therefore force a win when n is odd (by taking half the board).

Using induction:

Suppose n is even. Player 1 takes anything but a slab (which we know gives Player 2 a win because we've solved the n-1 case).

Then Player 2 takes whatever is radially opposed until player 2 is in a position to leave an odd number of single cubes. I think this "proof" needs a little more flesh, but I think it's a good "skeleton".

No, it doesn't work... if we have 2 2x2 square slabs with single pieces attached, it seems that the player to move has a winning move, in taking a whole square... I think this invalidates my general proof as well for 3^n (or boxes with at least one dimension > 3)...

However, my proof for 2 dimensions is still valid.

[Colymbosathon ecplecticos]

Let A(n) be the set of integers k <=n so that player 1 can force a win in dimension k, and let a(n) be the cardinality of A(n). By dimension k I mean a 3x3x...x3 (k-times) board.

Then, it is easy to see that liminf A(n)/n >= 1/2. I conjecture that it is 1.