Maths Olympiad Prep

Library / /100 of 155

Combinatorics Difficulty 6.4 National olympiad Prove it Saudi Arabia

Find the number of ways one can put numbers 11 or 22 in each cell of a 8×88 \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).

Solution

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×77 \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 77 numbers is odd, then we put 11 on the remain cell; otherwise, we put 22.

Figure 1

Finally, the number for the cell at corner can choose base on the parity of the sum of all number in square 7×77 \times 7. These mean that the way to fill in the square 7×77 \times 7 uniquely define the numbers on the rest cells.

Since we can fill each cell among 4949 cells of the square 7×77 \times 7 by 11 or 22 in any way then the number of way is 2492^{49}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.