Tuesday, September 19, 2006

Stop Drawing On the Checkerboard! Topic: Logic.

Problem: (2001 Putnam - B1) Let $ n $ be an even positive integer. Write the numbers $ 1, 2, \ldots, n^2 $ in the squares of an $ n \times n $ grid so that the $ k$th row, from left to right, is

$ (k-1)n+1, (k-1)n+2, \ldots, (k-1)n+n $.

Color the squares of the grid so that half of the squares in each row and in each column are red and the other half are black (a checkerboard coloring is one possibility). Prove that for each coloring, the sum of the numbers on the red squares is equal to the sum of the numbers on the black squares.

Solution: Consider all the values of the red squares $ r_1, r_2, \ldots, r_{k} $ and all the values of the black squares $ b_1, b_2, \ldots, b_{l} $. For each square (of any color) $ a_i $, let

$ a_i = R(a_i)n+C(a_i) $,

where $ R(a_i)+1 $ and $ C(a_i) $ are the row and column of the square corresponding to $ a_i $. We want to show that

$ \displaystyle \sum r_i = \sum b_i $.

But we have

$ \displaystyle \sum r_i = \sum R(r_i)n + \sum C(r_i) $ and $ \displaystyle \sum b_i = \sum R(b_i)n + \sum C(b_i) $.

Since each row has half red and half black, we have

$ \displaystyle \sum R(r_i)n = \sum R(b_i)n $

for each row and consequently the whole board. Similarly, since each column has half red and half black, we have

$ \displaystyle \sum C(r_i) = \sum C(b_i) $

for each column and hence the whole board. Adding these two equalities together, we obtain

$ \displaystyle \sum r_i = \sum b_i $

as desired. QED.

--------------------

Comment: Not too hard intuitively, but slightly difficult to put down a rigorous proof; assigning variables can be a good way of going about solving word problems. It might simplify the problem down to some simple algebra, which is good.

--------------------

Practice Problem: Let $ n $ be a positive even integer. In how many ways can we fill an $ n \times n $ board with $ 1 $'s and $ -1 $'s such that the sum of each row and column is zero?

4 comments:

  1. Practice Problem: 1/2 n^2 should be 1s and the other half should be -1s. hm...

    n^2 choose 1/2 * n^2 ways of doing it.

    wow, that took me like 20 min, and it's probably wrong...

    ReplyDelete
  2. That's a good start, but you'll have to figure out which of those cases have the sum of each row/column equal to zero. This problem is actually really hard and there apparantly is not a nice formula.

    http://www.artofproblemsolving.com/Forum/viewtopic.php?p=635604#635604

    ReplyDelete
  3. wow.. i looked at the thing, or the answers... and.. i would've never got that.
    do you post all your practice questions on the AOPS site?

    ReplyDelete
  4. Not all of them; mostly the ones I can't solve =).

    ReplyDelete