Number Board Puzzle: Sum of Colours
Source: Asked to me by Anuj Jain (EE IITB 2010 Graduate, MFE Student at Baruch College NY)
Problem:
You have a 8x8 square board with numbers in each cell.
Each number is given a colour (red or white) such that each row and each column has exactly the same number of red number and white numbers (i.e. four). Prove that the sum of 32 red numbers on the board is equal to the sum of the other 32 white numbers on the board.
Cheers!
Update (21 Jan 2012):
Solution: Posted by Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student) in comments!
Problem:
You have a 8x8 square board with numbers in each cell.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
| 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 |
| 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 |
| 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 |
Cheers!
Update (21 Jan 2012):
Solution: Posted by Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student) in comments!
Without loss of generality, subtract 1 from each number so that we have now 0...63. Now write each number in octal representation. So that all number are
ReplyDelete[00,01,02,03,...,07;
10,11,12,13,...,17;
.
.
.
70,71,72,73,...,77] = X
Now X=X1+X2
where X1 contains
[00,00,00,00,...,00;
10,10,10,10,...,10;
.
.
.
70,70,70,70,...,70] = X1
And
[00,01,02,03,...,07;
00,01,02,03,...,07;
.
.
.
00,01,02,03,...,07] = X2
Copy the coloring of X to X1 and X2
Now, consider sum of red in X call red(X)
red(X)=red(X1)+red(X2)
Now in X1, in any row all the entries are same, and half of them are red, similarly in X2 all the entries in a given column is same, and so by property of the coloring half of them are red, hence
red(X) = 4*(00+01+02...07)+4*(00+10+20...70) (in base 8)
and white(X), has also the same expression,hence equal.
idea of proof:
ReplyDeletelets think of x and y axis as two dimensions of the matrix. We can break the contribution to of the red/blue sum into x and y contributions.
for any element in red, we can find a blue element in blue on the same column (say a) and another element (say b) on the same row to this red element. The contribution of the red element to the red sum will be equal to the x-contribution of a plus the y-contribution of b. After this, we can take away the red element and the x contribution of a and y contribution of b and proceed. In the end, we will take away all elements and the red sum equals to blue sum in each step.
@Piyush.. Correct solution. Thanks
ReplyDelete@FZ.. I did not get your solution. But I think Piyush's solution is what you meant. :)
Each cell has a value based on its row and column number call it row contribution, column contribution
ReplyDeleteSum of all red cells = Sum of row contribution of all red cells + Sum of column contribution of all red cells
Sum of row contribution of all red cells = Sum over each row i (row contribution of 4 red cells ) = 4* (i-1)*8
Sum of column contribution of all red cells = Sum over each column j (column contribution of 4 red cells ) = 4* j
As this sum is independent of the actual position of red cells, it should be equal to the sum of white cells.
Yet another Solution:
ReplyDeleteGiven matrix:
M1 = [1,2,...7,8;
9,10,...17,18;
.
.
.
57,58,...63,64]
Consider the difference between red sum and white sum, say d1.
Since each row has 4 red and 4 white, subtracting each element of a row by a fixed value does not change the difference.
Hence, for the following matrix:
M2 = [0,1,2,...7;
0,1,2,...7;
.
.
.
0,1,2,...7] (8 rows)
Difference b/w red sum and white sum d2.
d2 = d1.
Now, in M2 each column has equal number of reds and whites. Hence red and white sums in each column is the same => d2=0 => d1=0
@kalyan, yashoteja..
ReplyDeleteYour solutions are basically restatement of piyush's solution (simply put though).
Thank You
You can divide the grid into 4 equal quadrants.
ReplyDeleteThe first part would be to ensure that the sum of all numbers of each color are equal.It is possible to find pairs of numbers in diagonally opposite quadrants that sum to 65.Each number in the pair should be of the same color. Hence we only need to select numbers in quadrant 1 and 2. Numbers in quadrant 3 and 4 are automatically selected to make the sum 65. This strategy would ensure that the sum of two colors are always equal.
The second part is to ensure that we arrange numbers such that there are exactly 4 of the same color along each row and column.
To do this we need to ensure that numbers in quadrant 1 and 2 about the Y axis and along the same row are opposite in color.This ensures that there only 4 numbers of the same color along each row.Our first strategy of selecting pairs in diagonally opposite quadrants ensures that there are only 4 numbers of the same color along each column.
The sum of each color would be 1040 = (65*16)
@Rohit Arora,
ReplyDeleteI did not get your solution. To clarify a possible confusion, you are given the square and the colours. You are not colouring the squares.
I tried to show a general pattern of coloring for the given condition and deduce that the sums were always equal for each case. In fact the pattern can be extrapolated to higher numbers. I just tried to highlight the symmetry in the problem that leads to equal sums
ReplyDeletewrite first row as
ReplyDelete4-3 4-2 4-1 4-0 4+1 4+2 4+3 4+4
second row as
12-3 12-2 12-1 12-0 12+1 12+2 12+3 12+4 so on so last row will be
60-.....
you know sum of red & white in 1st row is 16+x1 & 16+x2
similarly sum is 60+x15& 60+x16 in last row,
basically we want to show their sum is equal so we can minus 16,..., 60 from both sides
after doing it we will get first row as
-3 -2 -1 0 1 2 3 4
second as
-3 -2 -1 0 1 2 3 4
all rows are same.
now look at coloumns, sum of any four nos. is same because all are same.
so basically sum will be equal.
Yep. Same answer as provided by everyone. More difficult explanation though :) Thanks
DeleteI think this is the same answer as everybody else, but I'll put it up to check if it is right.
ReplyDeleteYou can generate every term in this table by the formula x + (y-1)8, where x is the column number and y corresponds to the row number. This formula suggests that we can take the given table and separate it into two tables. The first table looks like this:
0 0 0 0 0 0 0 0
8 8 8 8 8 8 8 8
16 16 16 16 16 16 16 16
24 24 24 24 24 24 24 24
32 32 32 32 32 32 32 32
40 40 40 40 40 40 40 40
48 48 48 48 48 48 48 48
56 56 56 56 56 56 56 56
The second table looks like this:
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
Adding these two tables together gives us the given table. By the question criteria, the number of reds and blues per row must be equivalent. Applying this to the first table, it's easy to see that the sum of the red numbers = the sum of the blue numbers in the first table. Similarly, applying the property that the number of blue and red numbers per column must be equivalent to the second table, it's easy to see that the sum of the blue = the red numbers in the second table. Since the sum of the blue numbers = the sum of the red numbers for both tables and the addition of these tables gives us the table from the question, it must be true that the sum of the blue numbers = the sum of the red numbers in the table given in the question.
I don't know if this constitutes a sufficient explanation...