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?

(In reply to Proof of optimality of 15 for 5x5 by David Shin)

David, I fear you are right, there is nothing I can say against your proof.  So far for the G.U.F.  Thanks for the proof, I could have tried forever without finding a better solution.  Maybe there is a different formula for even and odd grids.
In vain I made a program that put 14 lines at random and then checked the result, after a weekend, it had not found a solution. 

Now, why did I think that there was room for improvement?
In my postings, I used the word "overkill". by which I meant the following:
Overkill is when, by putting one line on the board, it is possible to make more then one completely closed square. 
In an ideal solution, there should only be the lines which are absolutely necessary, so an ideal solution has no overkill.

On the five points grid solution, if I label the points A to E horizontally and 1 to 5 vertically, there is overkill with the A3-B3, B2-C2 and B4-C4 lines.  So I hoped that maybe I could throw a line out.
On the 7 point grid, I still have seven overkill lines, so there improvement may be possible.  

Posted by Hugo on 2005-01-24 18:56:13