Maths Olympiad Prep

Library / /8 of 10

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it South Africa

The squares of an 8×88 \times 8 board are coloured alternatingly black and white. A rectangle consisting of some of the squares of the board is called important if its sides are parallel to the sides of the board and all its corner squares are coloured black. The side lengths can be anything from 11 to 88 squares. On each of the 6464 squares of the board, we write the number of important rectangles in which it is contained. The sum of the numbers on black squares is BB, and the sum of the numbers on white squares is WW. Determine the difference BWB-W.

Solution

In each important rectangle, the number of black squares is one more than the number of white squares. Hence, each important rectangle contributes +1+1 to the difference BWB-W. The value of BWB-W is thus the same as the number of important rectangles on the board.

Let us number the rows on the board 1,2,,81, 2, \ldots, 8 from the top downwards and the columns 1,2,,81, 2, \ldots, 8 from the left to the right. So (1,1)(1, 1) is the upper left square and (8,8)(8, 8) denotes the lower right square. Assume (1,1)(1, 1) is a black square. Then all (i,j)(i, j) with both ii and jj odd, as well as all those with both ii and jj even, are black squares. All other squares are white.

By focusing only on the four odd-numbered rows and the four odd-numbered columns, we find that they determine (4+(42))2=100(4 + \binom{4}{2})^2 = 100 important rectangles. Similarly, the four even-numbered rows and the four even-numbered columns determine another 100100 important rectangles, giving a total of 200200 important rectangles on the board. It follows that BW=200B-W = 200.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.