|
||
|
Title: Dots game Post by Altamira_64 on Jul 6th, 2012, 3:24am 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). |
||
|
Title: Re: Dots game Post by pex on Jul 8th, 2012, 8:56am 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 ... ... ....... ....... |
||
|
Title: Re: Dots game Post by towr on Jul 8th, 2012, 10:58am A strategy for when n=m, is to take everything but the first column and first row; then just mirror your opponent's move. |
||
|
Title: Re: Dots game Post by pex on Jul 8th, 2012, 11:24am on 07/08/12 at 10:58:37, towr wrote:
Hm, yes, obviously. Good catch - I wonder how I missed that. I guess you've also demonstrated why there's m≠ (http://www.codetable.net/decimal/8800)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. |
||
|
Title: Re: Dots game Post by 0.999... on Jul 9th, 2012, 6:54pm 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 mhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gifn (except the proof itself). The first person to play wins if and only if m is odd or |m-n|http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif1. 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. |
||
|
Title: Re: Dots game Post by pex on Jul 10th, 2012, 1:19am on 07/09/12 at 18:54:13, 0.999... wrote:
Should and be or? |
||
|
Title: Re: Dots game Post by 0.999... on Jul 10th, 2012, 6:51am Oops. Yes. |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |