Author |
Topic: Dots game (Read 831 times) |
|
Altamira_64
Junior Member
Posts: 116
|
We have a grid of m x n dots, where m is the number of rows and n the number of columns, m≠n and m, n >2.
.......
.......
.......
.......
.......
.......
Two players alternate turns and choose one dot from the grid and then pick all dots above and to the right of these dots. The purpose of the game is to force your opponent take the last dot.
Do I play first or second? What is the strategy to win?
...
...
...
...
.......
.......
(for example I chose the 4th dot of the 3rd row from the bottom, so I got all 16 dots above and to the right of this one).
|
|
 IP Logged |
|
|
|
pex
Uberpuzzler
Gender: 
Posts: 880
|
 |
Re: Dots game
« Reply #1 on: Jul 8th, 2012, 8:56am » |
 Quote  Modify
|
Interesting! I have brute-forced all rectangles up to 12x12, and it seems that all of them (except of course 1x1) are winnable by going first. I don't see a pattern in the winning moves yet, so I can't really comment on the winning strategy.
For the 6x7 case in your example, a (the?) winning first move is
....
....
.......
.......
.......
.......
and I have checked that your example move loses against best play; my response to it would be
...
...
.......
.......
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Dots game
« Reply #2 on: Jul 8th, 2012, 10:58am » |
Quote Modify
|
A strategy for when n=m, is to take everything but the first column and first row; then just mirror your opponent's move.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Dots game
« Reply #3 on: Jul 8th, 2012, 11:24am » |
Quote Modify
|
on Jul 8th, 2012, 10:58am, towr wrote:| A strategy for when n=m, is to take everything but the first column and first row; then just mirror your opponent's move. |
|
Hm, yes, obviously. Good catch - I wonder how I missed that.
I guess you've also demonstrated why there's m≠n in the problem statement...
Edit: for n=2 there is an easy strategy as well: take only the top right dot. Whatever your opponent does, you can always make sure that after your own move, the first column contains one more dot than the other.
|
| « Last Edit: Jul 8th, 2012, 12:50pm by pex » |
IP Logged |
|
|
|
0.999...
Full Member
Gender:
Posts: 156
|
|
Re: Dots game
« Reply #4 on: Jul 9th, 2012, 6:54pm » |
Quote Modify
|
If we have an L-shape of thickness 1 but with 1 dot in the lower left (i.e. :: with extensions upward and toward the right), then we can classify them by induction on, say, the height. So, let (m,n) indicate one of these with height m and length n and wlog m n (except the proof itself).
The first person to play wins if and only if m is odd or |m-n| 1.
I think I am closing in on some bigger results, but that is the only complete one at this point. For instance, (4,5) is the smallest L-shape of thickness 2 to lose for the first player.
|
| « Last Edit: Jul 11th, 2012, 4:54am by 0.999... » |
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Dots game
« Reply #5 on: Jul 10th, 2012, 1:19am » |
Quote Modify
|
on Jul 9th, 2012, 6:54pm, 0.999... wrote:| The first person to play wins if and only if m is odd and |m-n|1. |
|
Should and be or?
|
|
IP Logged |
|
|
|
0.999...
Full Member
Gender:
Posts: 156
|
|
Re: Dots game
« Reply #6 on: Jul 10th, 2012, 6:51am » |
Quote Modify
|
Oops. Yes.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print