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 shall prove that the optimal for a 5x5 game is 15. 

First, note that for each corner square, we must have exactly 2 edges drawn.  This gives 4*2=8 edges.

Now, look at the diagram below:

. . . . .
. . . . .
!_! . . .
! ! . . .
. . . . .

We see that either two edges denoted by ! must be drawn in or that the edge denoted by _ must be drawn in.  The same analysis holds for the analogous regions at the top, right, and bottom of the entire square.  Define a side of the square to be "singly-edged" if the _ edge is drawn in, and define it to be "doubly-edged" if two of the ! edges are drawn in.

If 3 or more of the sides are doubly-edged, we already have at least 8+3*2+1=15 edges.

If two of the sides are doubly-edged, we already have 8+2*2+2*1=14 edges, but the square is not yet complete in the inner regions.

If none of the sides are doubly-edged, we have no edges drawn in for the inner 4 squares.  We see that the 4 innermost edges must all be drawn in, which gives at least 8+4*1+4=16 edges.

If exactly one side is doubly-edged (as in Hugo's solution), we clearly see that the square needs at least 2 more edges, as no single edge can complete the following square:

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

(I've made an assumption in the above diagram about how the two edges per corner are drawn in, but the assumption is not necessary - it is the inner region of the square that cannot be completed by one edge)

Adding those 2 necessary edges yields the total of 8+2+3*1+2=15 found by Hugo.

This proves the optimality of 15 for a 5x5 square.

Posted by David Shin on 2005-01-15 18:24:57