SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
Advaita
Topic Author
Posts: 188
Joined: April 20th, 2005, 1:54 pm

White, Black, 1, 0

December 24th, 2007, 4:09 pm

1> Suppose on a chessboard of dimensions 1998 X 2002, there are 1's and 0's. 2> Now sum of every row is odd and sum of every column is odd.Then show that the total number of white cells with 1's is even.
 
User avatar
pk14
Posts: 85
Joined: February 15th, 2006, 12:43 am

White, Black, 1, 0

December 24th, 2007, 5:58 pm

We denote the total number of the white cells with 1 by X.Let C be the matrix which represents the 0,1's on the chessboard.Let H_a be the sum of the a-th row of C and L_b be the sum of the b-th column of C.Consider the sumWe claim S is the sum of all white 1's with +2 or -2 in front of them. This is because the white cells correspond to the coefficients of C whose column number and row number are both even or both odd. Black cells cancel out when we form the sum because they correspond to coefficients whose column number and row number are different modulo 2.Its easy to see that S = 2*X (mode 4) . And from the condition given by the problem, it is very easy to see S = 0 (mode 4) (To prove this, we only need to use are all odd as stated in the problem and the equality which is obviously true given the definitions of ). Hence X is even.
Last edited by pk14 on December 23rd, 2007, 11:00 pm, edited 1 time in total.
 
User avatar
Advaita
Topic Author
Posts: 188
Joined: April 20th, 2005, 1:54 pm

White, Black, 1, 0

December 24th, 2007, 6:24 pm

Wow. Does this work for 1000X1000 matrix also? In my mind, you can rearrange the strips to get the re-arranged board:W1 B1B2 W2each of the four sub-matrices is 999 X 1001 (W means all whites, B all blacks). And the column and row rule still holds.Now taking mod 2,Sum(W1) + Sum(B1) = 1 (sum of 999 rows)Sum(W2) + Sum(B1) = 1 (sum of 1001 columns)Adding this gives Sum(W1) + Sum(W2) = 0
 
User avatar
pk14
Posts: 85
Joined: February 15th, 2006, 12:43 am

White, Black, 1, 0

December 24th, 2007, 7:07 pm

Using my argument, 1000 by 1000 can be proved in the same way (a little bit easier actually).I like your proof. It's interesting.
 
User avatar
pk14
Posts: 85
Joined: February 15th, 2006, 12:43 am

White, Black, 1, 0

December 24th, 2007, 7:45 pm

It feels like Rubik's cube way of sorting. Interesting.
Last edited by pk14 on December 23rd, 2007, 11:00 pm, edited 1 time in total.
 
User avatar
Advaita
Topic Author
Posts: 188
Joined: April 20th, 2005, 1:54 pm

White, Black, 1, 0

December 26th, 2007, 1:13 pm

Yes the problem is for 2*(2n+1) X 2*(2m+1) board, from Titu Andrescu's book but he gives a somewhat complicated proof.Also by re-arranging a chessboard I mean --1. rotate it so that white is at topmost left.2. Now take all the odd-numbered vertical strips and move them to the left. THe sum conditions are still met.3. Now from this re-arrangment, take all alternating horiz. strips and move them to top. THe sum conditions are still met. 4. THis gives a four color board.
 
User avatar
pk14
Posts: 85
Joined: February 15th, 2006, 12:43 am

White, Black, 1, 0

December 26th, 2007, 5:36 pm

Great.My proof is actually very straight forward as well.
 
User avatar
NE1
Posts: 88
Joined: August 5th, 2002, 11:36 pm

White, Black, 1, 0

December 30th, 2007, 2:38 pm

QuoteOriginally posted by: AdvaitaWow. Does this work for 1000X1000 matrix also? In my mind, you can rearrange the strips to get the re-arranged board:W1 B1B2 W2each of the four sub-matrices is 999 X 1001 (W means all whites, B all blacks). And the column and row rule still holds.Now taking mod 2,Sum(W1) + Sum(B1) = 1 (sum of 999 rows)Sum(W2) + Sum(B1) = 1 (sum of 1001 columns)Adding this gives Sum(W1) + Sum(W2) = 0Very nice proof there! For a 1000x1000 board, or in general NxN board one can start with a 1x1 white square. That obviously has a sum over white squares of 1 or odd. Now add a row and a column to this to make it a 2x2 board. Again it is easy to see that the sum is now zero or 2 which is even. Add another row and column to make a 3x3 board and the sum has switched back to odd again. It follows that the sum is even when N is even and odd when N is odd for any NxN board. Do this all the way to a 1998x1998 board and the sum is still even. To get to the 1998x2002 board we have to attach four columns to the square board. Each column must sum to an odd number obviously and the sum of each row must be even so that the new columns would not mess up the constraint on the sum of each column and row be odd. One can play the same game with a 1x4 board and then grow it to 1998x4 to see that this board (which is to be attached to the 1998x1998 board) has an even sum over the white squares. Then the full board 1998x2002 is still even. This is no where as neat as Advaita's proof but it is another way.
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On