SAUDI ARABIAN MATHEMATICAL COMPETITIONS

Question

Find the number of ways one can put numbers

1

or

2

in each cell of a

8 \times 8

chessboard in such a way that the sum of numbers in each column and in each row is an odd number (two ways are considered different if the number on some cell in the first way is different from the number on the cell at correspondent position in the second way).

Accepted Answer

Consider the leftmost column and lowest row of table, we color all these cells. We can see that for all ways to put the number of the sub square

7 \times 7

that not colored, we can choose the number for the correspondent colored position at same column or row. Indeed, if sum of the

7

numbers is odd, then we put

1

on the remain cell; otherwise, we put

2

.

Finally, the number for the cell at corner can choose base on the parity of the sum of all number in square

7 \times 7

. These mean that the way to fill in the square

7 \times 7

uniquely define the numbers on the rest cells.

Since we can fill each cell among

49

cells of the square

7 \times 7

by

1

or

2

in any way then the number of way is

2^{49}

.