Maths Olympiad Prep

Library / /122 of 860

Combinatorics Difficulty 4.8 AIME Find the answer

Given a 9×99 \times 9 chess board, we consider all the rectangles whose edges lie along grid lines (the board consists of 81 unit squares, and the grid lines lie on the borders of the unit squares). For each such rectangle, we put a mark in every one of the unit squares inside it. When this process is completed, how many unit squares will contain an even number of marks?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

56. Consider the rectangles which contain the square in the iith row and jjth column. There are ii possible positions for the upper edge of such a rectangle, 10i10-i for the lower edge, jj for the left edge, and 10j10-j for the right edge; thus we have i(10i)j(10j)i(10-i) j(10-j) rectangles altogether, which is odd iff i,ji, j are both odd, i.e. iff i,j{1,3,5,7,9}i, j \in\{1,3,5,7,9\}. There are thus 25 unit squares which lie in an odd number of rectangles, so the answer is 8125=5681-25=56.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.