wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Game removing objects from an n x n grid
        
(Message started by: jollytall on Jul 20^th, 2007, 1:18am)

Title: Game removing objects from an n x n grid
Post by jollytall on Jul 20^th, 2007, 1:18am

Inspired by the game (also discussed here earlier) where there are 3, 5 and 7 objects arranged in three rows. Two players take any number >0 objects from any row (but only one row). That wins who does NOT take the last object.

Now, the same a bit differently: The objects are arranged in an n x n matrix. Any number of objects can be removed from any row OR column. There is no restriction that the objects removed in one go must be neightbours, they only have to be in one row or one column. There are two sub-variants, re who wins (who takes or who does not take the last one).
Who has a winning strategy? How?

For n=2 it is easy that regardless the sub-variant the second player has a winning strategy. From n>2 it gets more tricky.

Title: Re: Game removing objects from an n x n grid
Post by Grimbal on Jul 20^th, 2007, 1:29am

If n is even and the goal is to take the last item, the ~~first~~ last player wins:
[hide]Use central symmetry.[/hide].

Title: Re: Game removing objects from an n x n grid
Post by jollytall on Jul 20^th, 2007, 3:29am

Probably you mean the opposite: [hide]A takes something, B takes the opposite, then B can win.[/hide]

Title: Re: Game removing objects from an n x n grid
Post by towr on Jul 20^th, 2007, 3:52am

And when n is odd, [hide]the first player can win by taking the middle and using the same reasoning for the rest to end up with the last object(s).[/hide]

Title: Re: Game removing objects from an n x n grid
Post by jollytall on Jul 20^th, 2007, 7:11am

Not really. You remove the middle, I remove the whole middle row. What will you take? Then of course you can use even more symmetry (the middle column, e.g.) but this is not that obvious.

The original game is only interesting when you should not take the last one. It might be the case here, too.

Title: Re: Game removing objects from an n x n grid
Post by towr on Jul 20^th, 2007, 7:13am

on 07/20/07 at 07:11:44, jollytall wrote:

Not really. You remove the middle, I remove the whole middle row. What will you take? Then of course you can use even more symmetry (the middle column, e.g.) but this is not that obvious.

Seems obvious to me.. Nevermind that that reduces it to an the even case

Title: Re: Game removing objects from an n x n grid
Post by jollytall on Jul 20^th, 2007, 7:33am

That is obvious to me, that if you take the middle piece and I take the whole middle row, then you take the whole middle column and so you can still win. My point was that then it is not central symmetry anymore, i.e. you did not get back to the Grimbal solution. You use a C4 symmetry (if I remember correctly the naming) not a C2.

But there is another problem with your logic, if I do not take the middle row as the first step, but as the last one. I.e. You take the middle piece. I take the first row, you (with a simple symmetry logic) take the last row, etc. In the last step I take the whole middle row and I win (you do not have a C2 or C4 symmetry left).

I do not say, btw., that the winning strategy is not on the first player's side, but I still do not think it is obvious. (Someone has the signature under his posts: Obvious is the most dangerous word in math.)