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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum