Home > Problem of the Week > Archive List > Detail

 << Prev 6/5/2011 Next >>

Create an N x M rectangular array of dots, where both N and M are even. Color the dots either yellow or blue in such a way that every row has an equal number of yellow dots and blue dots...plus, every column has an equal number of yellow dots and blue dots.

Note: I suggest you start with a reasonably small N and M (e.g. N = 4, M = 6), as the task of coloring in the dots to fit the requirements is not a trivial matter.

Now, whenever two dots of the same color are adjacent in the same row or column, connect them with a line segement of the same color.

True or False: The total number of blue segments will always equal the number of yellow segments.

And, if you like to extend problems, try the same problem starting with a N x M x P rectangular array of dots, again where all three dimensions are even....and then generalize to a N1 x N2 x N3 x ... x Nk "rectangular" array.

Source: S. Maurer, American Mathematical Monthly, September, 1971, p. 796

Y B B B Y Y
Y Y Y B B B
B B Y Y Y B
B Y B Y B Y
Does the suggested relationship hold?

Now focus on a sub-case with N=2. What do you notice....

Solution Commentary: It is TRUE! A summary of Maurer's solution follows...

Draw a rectanglar array that has exactly two columns (or exactly two rows). Call a dot in either column matched if it is of the same color as the dot beside it in the other column; otherwise call it mismatched. Thus, two matched dots will produce a line of the same color.

Since both columns have the same number of yellow dots and the same number of matched yellow dots, they will also have the same number of mismatched yellow dots. But, the number of mismatched yellow dots in one column will equal the number of mismatched blue dots in the other column, as they are adjacent.

Thus (i.e. think carefully), within either column, the number of mismatched yellow dots will equal the the number of mismatched blue dots. But, this implies that the number of matched yellow dots equals the number of matched blue dots, as in each column, the number of yellow dots equals the number of blue dots.

Now, this argument is sufficient for a similar argument for the any rectangular array fitting the initial conditions, as it becomes a mere process of addition of equals.