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 suspect being able to draw a diagram will be especially useful in this problem, and perhaps in others.  Here are some instructions for those who don't know how. I hope they help! :)

First, press enter to start a new paragraph.  Then, press "Formatting >>" and "Pre-Formatted".**  If you type anything in that paragraph, it will be monospaced..

...like this!  To revert back, press "formatting >>"
again, and press "Normal".

While in monospaced font, numbers and lines will line up...

...like this: 123 /-
              456 _/

Also, note that if you keep on typing on the same line in monospace, it will NOT wrap to the next line.  Please press enter to go skip a line or shift-enter to go to the next line.  If not, your comment will be really wide (and annoying), and people will have to scroll to the right to read it.

So, if you want to draw your solution for this problem, you probably want to go into monospace font, and use lines and underlines.  To make lines "|" press shift (the key is below the backspace).  To make underlines "_" press shift- (the key is to the right of 0.

If you make a mistake, don't hesitate to edit your comment to fix it!

My diagrams would end up looking something like this:

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

Have fun!

**I'm told that sometimes these buttons don't appear, depending on your browser.  In general, there seem to be a lot of browser compatibility problems with this comment editor.  Use explorer if you have to.

Edited on January 12, 2006, 8:28 pm

Posted by Tristan on 2005-01-05 01:42:57