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?

Well, I was making the same mistake as Hugo.
I was trying to maximize instead of minimize.

But, it seems the basics remain the same.
While maximizing, you have to use all the edges on the grid.
While minimizing, you have to use none.

While maximizing, you have to make concentric squares.
While minimizing, you have to turn concentric squares inside out.

For eg:
For 5*5 square:

_| | |_
___|___
_  |  _
 | | |

For 6*6 square:
_| | | |_
___| |___
___   ___
_  | |  _
 | | | |
 
So on and so forth
 
In general,
For odd number of dots, minimum lines = (n-1)^2
For even number of dots, 
minimum lines = ((n-1)^2)-1 (for n> 2)
 

Posted by Milind on 2005-01-06 07:16:38