Grid with 14 Dots

Date: 11/10/97 at 18:41:01
From: Sarah Schuldenfrei
Subject: Grid with 14 dots

In an enrichment project at school we had this problem:

Make a 6 by 6 grid. In this grid, put dots in 14 squares. There 
must be an even number of dots in every row and column (zero is even). 

I figured out this solution:

- - - - - -
- . . - . .
- . - . - -
- - - . - .
- . . - . .
- . - - - .

Is there any rule for building solutions to this problem?
If so, what is the rule?

Date: 11/11/97 at 10:52:33
From: Doctor Ken
Subject: Re: Grid with 14 dots

Hi Sarah -

That's a really neat problem! Congratulations on coming up with a 
solution; that's impressive. 

Here are some things you might think about when trying to come up with 
other solutions to this problem.

First of all, what would happen if you switched two columns in a 
solution, like this:

| | | * # |               | | | # * |
| | | * # |               | | | # * |
| | | * # |               | | | # * |
| | | * # |    becomes:   | | | # * |
| | | * # |               | | | # * |
| | | * # |               | | | # * |


If we did this to your solution, here's what the result would be:

- - - - - -
- . . . - .
- . - - . -
- - - - . .
- . . . - .
- . - - - .

Is this also a good solution? Well, it has the right number of dots 
(14), since we didn't add any more dots and we didn't take any away, 
we just moved them around. And if you check, there is still an even 
number of dots in each row and column. So this is another solution!

Now, do you think we could _prove_ that starting with one solution 
and switching columns like this will always lead to another solution?  
I bet we can. First we have to show that the result has the right 
number of dots (14), and then we have to show that the result has an 
even number of dots in each row and column.

First part: showing that there are 14 dots in the result

   This is pretty believable, since we're not taking any dots away or 
   making any new ones, we're just moving them around.

Second part: showing that there is an even number of dots in each 
             column

   If we start with an even number of dots in the two columns we're 
   switching, then since we carry all the dots in those two columns 
   with us when we switch, we'll still have an even number in those 
   columns when we're done.

Second part: showing that there is an even number of dots in each row

   When we switch two columns with each other, we only move dots from 
   side to side, not up and down, so there will still be the same 
   number of dots in every row as there were before we moved things 
   around. So the number in each column will still be even.

So now we know we have a method for making lots and lots of solutions 
to your problem! Now here's a question: what happens if we switch two 
_rows_  instead of two columns? Maybe you can convince yourself that 
the same kind of thing will happen, you'll still end up with a valid 
solution. So if you start out with any solution to this problem and 
keep switching rows and columns around however you want to, you'll be 
able to come up with lots and lots of solutions to your problem.

An interesting question would be "how many different solutions are 
there to this problem, and can we come up with a method for listing 
them in some systematic way?" I don't know the answer to that 
question. Perhaps you can use the switching rows and columns idea to 
figure it out, but it might be a really hard question, so don't feel 
bad if you can't!

-Doctor Ken,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/