My friend and I used to play a simple game. An abitrarily large array of dots was drawn on paper, and we took turns connecting adjacent dots vertically or horizontally. Whenever a box connecting four adjacent dots was made, the player who finished it got an extra turn and a point. When all possible lines were drawn, the game ended and the one with the most points won.

My friend and I were both horrible at this game; we both used the same ineffective strategy. On each of our turns, when possible, we would always make a move that would not allow the other player to make a box the next turn.

Using this strategy and 25 dots in a 5x5 grid, what is the fewest number of moves possible before someone has to let the other player score? What if we use 36 dots in a 6x6 grid? And 49 dots in a 7x7 grid?

I know that the problem asks for a minimum, but I'd just like to point out that some of the earlier conjectures on the maximum were incorrect.  For example, a 5x5 can be done in 24, while a 7x7 can be done in 48:

 _ _ _ _
|   |   |
|_ _|_ _|

|   |   |
|_ _|_ _|

---------------------------

 _ _ _ _ _ _ 
|   |   |   |
|_ _|_ _|_ _|
|   |   |   |
|_ _|_ _|_ _|
|   |   |   |
|_ _|_ _|_ _|

Edited on January 15, 2005, 5:48 pm

Posted by David Shin on 2005-01-15 17:43:33