Author |
Topic: Squares on a grid (Read 2092 times) |
|
Garzahd
Junior Member
Gender: 
Posts: 130
|
 |
Squares on a grid
« on: Oct 25th, 2002, 12:58pm » |
 Quote  Modify
|
Just recalled this problem that I read a long time ago. It was listed in a book as an unsolved problem, but it didn't seem that tricky to me. Perhaps that means my solution is wrong, but I'll throw it in and let people think about it.
You're playing a game with your friend on an infinitely large piece of graph paper. You and a friend each have a different color pen. You take turns marking intersections of the grid. The winner is the first person to color 4 intersections that form a square. The square may be of any size, but it must be oriented in the direction of the grid; that is, something like the midpoints of each side of a 2x2 square won't qualify.
What is the optimal strategy for each player? Who wins?
|
| « Last Edit: Oct 23rd, 2003, 7:36pm by Icarus » |
 IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: New puzzle: Squares on a grid
« Reply #1 on: Oct 25th, 2002, 1:41pm » |
Quote Modify
|
on Oct 25th, 2002, 12:58pm, Garzahd wrote:| What is the optimal strategy for each player? Who wins? |
|
Methinks that the person who goes first wins  Interesting problem!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: New puzzle: Squares on a grid
« Reply #2 on: Oct 27th, 2002, 8:05am » |
Quote Modify
|
I think that in optimal playing neither can win..
To make a square you need 4 points, to prevent someones square you need mark just 1 point..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: New puzzle: Squares on a grid
« Reply #3 on: Oct 27th, 2002, 11:18pm » |
Quote Modify
|
If my opponent place a dot along one of the imaginary lines connecting the corners of a square, does that block the formation of a winning square? In other words, if red dots are at (0,0), (0,2), (2,2), and (2,0), and a blue dot is at (0,1), has blue blocked red's win?
If such blocking is not allowed, I think you can show that the first player can always force a win in six moves. If you don't believe me, let's play for money  My first move is (0,0).
|
| « Last Edit: Oct 27th, 2002, 11:21pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: New puzzle: Squares on a grid
« Reply #4 on: Oct 28th, 2002, 12:29am » |
Quote Modify
|
well, one can't really play for money over the internet.. And I wouldn't.. but for the sake of argument, I'll play (1,0)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: New puzzle: Squares on a grid
« Reply #6 on: Oct 28th, 2002, 6:50am » |
Quote Modify
|
The person going first can win. Here is the beginning of my proof:
Player A goes first and WLOG (without loss of generality) places his piece at location (0,0).
Player B goes right beside him (I believe this is the best he can do). He goes in location (-1,0) or in location (-1,-1). I think (-1,0) is the better choice, but he will lose either way.
Player A goes in location (2,0).
Now player B has a choice. There are two essential qualities about his next play. It will:
i) Provide or not provide an opportunity to make a square with his first piece
ii) Prevent or not prevent player A from making at least one of the following four squares: (2,0)-(0,2), (2,0)-(4,2), (2,0)-(0,-2), (2,0)-(4,-2).
If he fails to do BOTH of these things, then he will definitely lose--if he fails to do i), then player A gains a turn, and can make an unblocked line of 3 (fatal for player B). If he fails to do ii), then player A will play (2,2), then (4,0), then (2,-2), forcing player B's move each time, then GAME OVER!
Now that we have that out of the way, player B is forced to play in location (4,0), since it is the only one that satisfies both i) and ii).
Player A can now win if he keeps forcing player B's moves, and never allows player B to get three points of a square. Here's how he does it:
A: (2,2)
B: (0,2)
A: (2,-2)
B: (0,-2)
A can now graduate to a larger grid size:
A: (6,2)
B: (6,-2)
A: (2,6)
B: (6,6)
Now A has formed an unblocked line of 3. B is toast:
A: (-2,2)
B: Yikes! (-2,-2)
A: (-2,6) for the win
If, at any point, A gives up the initiative and allows B to force his next move, then B will win. Basically, the person forcing the moves can always dominate. This is, for instance, why A can't play (1,0) after B's second move, making a doubly-unblocked line of 3 (which would win, except that B will keep forcing A's moves until B wins).
Note that the location of B's first move is unimportant, since A can always pick his second move so that B's first move doesn't block any of the four squares I talked about earlier. In fact, if B's first move is far enough away from A's first move, then A can pick his second move so that B's second move cannot satisfy both i) and ii) above, making an even easier win for A.
A good proof: cryptic, handwavy, entirely unconvincing, but true!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: New puzzle: Squares on a grid
« Reply #7 on: Oct 28th, 2002, 8:48am » |
Quote Modify
|
well, even if I'm bound to loose, I won't give up..
(0,8)
|
| « Last Edit: Oct 28th, 2002, 8:50am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: New puzzle: Squares on a grid
« Reply #9 on: Oct 28th, 2002, 1:04pm » |
Quote Modify
|
(so far, (0,0) (0,1) (8,0) (0,8) (0,-8) )
thus (8, -8)
|
| « Last Edit: Oct 28th, 2002, 1:07pm by william wu » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: New puzzle: Squares on a grid
« Reply #10 on: Oct 28th, 2002, 1:10pm » |
Quote Modify
|
(towr: sorry i goofed on my last move ... let's change that to (0,-8). glad i didn't play for money :P so then you respond with (8,-8) to block a win.)
(0,-4)
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: New puzzle: Squares on a grid
« Reply #11 on: Oct 28th, 2002, 1:15pm » |
Quote Modify
|
hehe.. yes.. Now I see..
I choose either (-4 4) or (-4, -4)
And then you do (-4,-4) or (-4,4) respectively. And then I loose after the next move..
I understand now =)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: New puzzle: Squares on a grid
« Reply #12 on: Oct 28th, 2002, 1:20pm » |
Quote Modify
|
I can prolong the inevitable with (1,7)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: New puzzle: Squares on a grid
« Reply #13 on: Oct 28th, 2002, 1:53pm » |
Quote Modify
|
Yeah. Basically, player 2's initial moves are somewhat meaningless, and player 1 can keep player 2 on the run until a doomsday scenario is created.
Not sure how (1,7) prolongs things ... are you saying you want to finish this game just for the sake of finishing? If so,
(4,4)
[ so far ]
(0,0) (0,1)
(8,0) (0,8)
(0,-8) (8,-8)
(0,4) (1,7)
(4,4)
|
| « Last Edit: Oct 28th, 2002, 2:01pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: New puzzle: Squares on a grid
« Reply #14 on: Oct 28th, 2002, 11:00pm » |
Quote Modify
|
oops.. I made the mistake now, I meant (7,1)
(as in a chance for square (0,1) (7,1) (0,8) (7,8))
after that you'd have to do (7,8) cause else I'd win..
then I could have tried the same on the other side with (-7 1)
and you'd have to do (-7, 8)
then I could do (-7,-6) etc.. actually it could go on for a while..
If you're willing to repair my move to (7,1) I'd be willing to keep trying from there.. It seems I have a chance after all.. At least to significantly prolong the game..
|
| « Last Edit: Oct 28th, 2002, 11:03pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: New puzzle: Squares on a grid
« Reply #15 on: Oct 29th, 2002, 2:51am » |
Quote Modify
|
Actually I goofed again, I just played a losing game. My 4th move of (0,4) was nonthreatening and thus allowed you to take the offensive and eventually win ... bleh. Maybe I should just retire from this site and go to sleep. No more drugs for me! :P
Mr. Fingas's nifty analysis explains how player 1 can guarantee victory in at most 8 moves (not 6). All of player 1's moves after the 2nd move have to be threatening. In the first phase, player 1 threatens twice to build a square of edge length n, and then threatens to build a square of edge length 2n and eventually wins. Here's a correction of the game we just played, given that your first two moves are (0,1) and (0,8). All your moves after the first two are fixed.
me you
(0,0) (0,1)
(8,0) (0,8)
(0,-8) (8,-8)
(-8,0) (-8,-8)
(8,16) (-8,16)
(24,0) (24,16)
(8,-16) i have 2 ways to win ((24,-16) and (-8,-16)), so forfeit
|
| « Last Edit: Oct 29th, 2002, 2:54am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: New puzzle: Squares on a grid
« Reply #16 on: Oct 29th, 2002, 3:30am » |
Quote Modify
|
hehe.. good thing we didn't play for money 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: New puzzle: Squares on a grid
« Reply #17 on: Oct 29th, 2002, 3:34am » |
Quote Modify
|
Seriously
Now what happens if winning squares can't have their edges interrupted by opponent pieces?
|
| « Last Edit: Oct 29th, 2002, 3:35am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: New puzzle: Squares on a grid
« Reply #18 on: Oct 29th, 2002, 8:18am » |
Quote Modify
|
I would say that makes it very easy to keep the other player from winning.. And so it'd be a tie..
(Well, actually when the saner of the two gives up the other would win by default..)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: New puzzle: Squares on a grid
« Reply #19 on: Oct 29th, 2002, 9:34am » |
Quote Modify
|
Yeah, it sounds impossible to force a win. After playing it out a bit on paper, it's ridiculously easy to stop somebody, and to ruin their chances to reuse their pieces in a larger sized square. Besides, any square bigger than 2x2 gives a large number of opportunities to stop it.
I've been thinking: what if the two players cooperated? Could they build up a pattern of dots that didn't contain any squares of either colour? This is similar to another question about colouring every point in the real plane with 2 colours and not making triangles, but, I believe, harder to answer.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: New puzzle: Squares on a grid
« Reply #20 on: Oct 29th, 2002, 11:26am » |
Quote Modify
|
So I started browsing the internet for this problem, which I tend to do once I've reached the conclusion that I have little left to analyze.
Found an interesting variant: Player 2 gets two moves for each one move of player 1, but he's no longer trying to get a box himself, only to prolong the game indefinitely. The site implied (but did not explain) that player 1 still has a winning strategy. So, is there a way for player 1 to craft a triple threat?
Looks like the game tree for this would get even more absurd. I do have a theory I'm pursuing, though.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print