Mathematical Food for Thought

  
 
 

  • About

    Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.
  
Stop Drawing On the Checkerboard! Topic: Logic. September 19th, 2006

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 kth 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?

Posted in AIME, Logic || 4 Comments »

4 Responses to “Stop Drawing On the Checkerboard! Topic: Logic.”

  1. Xuan Says:
    September 22nd, 2006 at 11:55 pm

    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…

  2. paladin8 Says:
    September 23rd, 2006 at 10:08 am

    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

  3. Xuan Says:
    September 23rd, 2006 at 11:00 pm

    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?

  4. paladin8 Says:
    September 23rd, 2006 at 11:57 pm

    Not all of them; mostly the ones I can’t solve =).

Leave a Reply

You must be logged in to post a comment.
Google

 

  
 
free web counters
Etronics