Author |
Topic: Square Game Strategy (Read 509 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
Square Game Strategy
« on: Dec 24th, 2003, 9:44am » |
 Quote  Modify
|
Consider the following game between 2 players:
They are given a plain made of m[times]n squares. Each players (in his turn) picks one of the (remaining) squares, and removes all the squares that are “below it and to its right” (i.e. if a player choose (i, j) square then all the (i', j') squares s.t. i'[ge]i, j'[ge]j are removed). The loser of the game is the player that chooses the upper/left most square (e.g. square (1, 1)).
1) Suppose n > 1 and m=n. Describe a (very) simple winning strategy for the first player.
2) Suppose m,n > 1. Prove the existence of winning strategy for the first player in the game.
3) Suppose m,n > 1. Devise a winning strategy...
Remark: I don't know the solution to (3) or if it even exists...
|
| « Last Edit: Dec 24th, 2003, 9:45am by Dudidu » |
 IP Logged |
|
|
|
Quetzycoatl
Newbie
Gender: 
Posts: 46
|
|
Re: Square Game Strategy
« Reply #1 on: Dec 26th, 2003, 11:48am » |
Quote Modify
|
I think perhaps I am misunderstanding the game, because it seems to me that the first player can always win by choosing the square at (2, 2), leaving only squares (1, 2) and (2, 1) and the losing square (1, 1). The opponent then chooses one of the two non-losing squares, then player 1 takes the remaining one leaving only the losing square.
I assume there is more to it than this so please explain what I am missing.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Square Game Strategy
« Reply #2 on: Dec 26th, 2003, 6:19pm » |
Quote Modify
|
That is part of a strategy, but you are mistaken that only (1, 1), (2, 1), and (1, 2) are left behind. (1, k), and (j, 1) are also left behind for all k <= n, j <= m. This leaves many possibilities for player 2. You must figure out player 1 must respond.
Problem (1) is easy to solve. I assume (2) can be shown by means of strategy - stealing (the most common means of showing a strategy must exist without actually producing one). But I have not thought it out as to how.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Square Game Strategy
« Reply #3 on: Dec 29th, 2003, 10:03am » |
Quote Modify
|
Here are some winning positions (after your turn):
x
xx
x
xx ... xx
xx ... x
xxx
x
x
xxxx
x
x
x
x ... xxx
x ... x
xx
x ... xxxx
x ... x
xxx
xxxxx
xxxxx
xxx
xxxxxxx
xxxxxxx
xxxx
Here is my contribution towards part 2, but notice that it is not complete. I think we need to delve a little into question 3 to complete it.
To prove that a winning strategy must exist, imagine the game tree for this game. It is a directed acyclic graph with a single "final node". Colour the nodes according to the following scheme:
1) First colour the final node blue. This is the game position with only one square left. Add it to B, the set of blue nodes.
2) Next, colour pink all the nodes V such that there is an edge from V to a node in B, and add them to P, the set of pink nodes.
3) Now find all nodes V such every edge from V goes to a node in P. There must be at least one such node. Colour all such nodes blue and add them to B.
4) Repeat 2 and 3 as needed (i.e. until the game tree node corresponding to the rectangular mxn grid has been coloured either pink or blue.)
There is a winning strategy for the starting player if the mxn grid is coloured pink, and there is no such strategy if it is coloured blue. I am relatively sure that the following grid sizes are coloured pink:
1xn
2xn
3xn
As for the other grid sizes, I just don't know. The winning strategy is to play to a blue node every turn.
|
| « Last Edit: Dec 29th, 2003, 10:04am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Square Game Strategy
« Reply #4 on: Dec 31st, 2003, 12:52am » |
Quote Modify
|
on Dec 29th, 2003, 10:03am, James Fingas wrote:| Here are some winning positions (after your turn)... |
|
James hi,
you gave many positions that may lead to a win, but can you give a recipe (i.e. algorithm) what is the first step that the first player should take, what is the second step he/she should take (in response to the second player's first step) ?
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Square Game Strategy
« Reply #5 on: Dec 31st, 2003, 7:48am » |
Quote Modify
|
I think the solution to this will not be an algorithm to say what the appropriate move is, but rather an algorithm to decide which positions are winning positions. Figuring out the most appropriate move from that is relatively easy.
I don't have such an algorithm yet, however. It looks like it will be a very complex (complexity O(mn) maybe) to specify the winning positions. But it's still an interesting problem...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Square Game Strategy
« Reply #6 on: Dec 31st, 2003, 8:19am » |
Quote Modify
|
on Dec 31st, 2003, 7:48am, James Fingas wrote:| I don't have such an algorithm yet, however. It looks like it will be a very complex (complexity O(mn) maybe) to specify the winning positions. But it's still an interesting problem... |
|
James, we're probably refering different things  .
I'm looking for an "algorithm" to the 1st sub-question (since altough it is quite easy, no one (yet) has suggested a correct strategy) while you are probably refering the 3rd sub-question...
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Square Game Strategy
« Reply #7 on: Dec 31st, 2003, 8:29am » |
Quote Modify
|
The winning positions I gave are relevant to the third sub-question more than to the first. The answer to the first sub-question is trivial given the winning positions I've already found:
Remove the (2,2) square, then mirror your opponents moves on the x=y line. Eventually, only the (1,1) square will be left, and it will be your opponent's turn.
|
| « Last Edit: Dec 31st, 2003, 8:30am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Square Game Strategy
« Reply #8 on: Dec 31st, 2003, 8:52am » |
Quote Modify
|
on Dec 31st, 2003, 8:29am, James Fingas wrote:| The winning positions I gave are relevant to the third sub-question more than to the first. The answer to the first sub-question is trivial given the winning positions I've already found... |
|
James,
Your answer to the first sub-question is correct (of course), well done !
Anyway, the second sub-question does not depend on the third sub-question (that can be easily regarded as hard). So, you don't have to solve it (i.e. the third one) in order to "get" the second one...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print