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?

Solution:

For a 5 X 5 grid, the solution is 24 steps
For a 6 X 6 grid, the solution is 36 steps
so on and so forth.

In general, for a n X n grid:
if n is odd, number of steps = (n * n) -1
if n is even, number of steps = (n * n)

Here the steps are all concentric squares.

Reasoning:
To maximize the steps, every dot (or maximum dots) in the grid should pass through 2 lines.
After this, if a dot passes through 3 lines, then the other player will be able to complete the box

Posted by Milind on 2005-01-04 20:41:01