HMMT 二月 2002 · ADV 赛 · 第 8 题

英文解析

8. Given a 9 × 9 chess board, we consider all the rectangles whose edges lie along gridlines (the board consists of 81 unit squares, and the grid lines lie on the borders of the unitsquares). For each such rectangle, we put a mark in every one of the unit squares insideit. When this process is completed, how many unit squares will contain an even number ofmarks?
   Solution: 56 . Consider the rectangles which contain the square in the i th row and j thcolumn. There are i possible positions for the upper edge of such a rectangle, 10 − i for thelower edge, j for the left edge, and 10 − j for the right edge; thus we have i (10 − i ) j (10 − j )
   rectangles altogether, which is odd iff i, j are both odd, i.e. iff i, j ∈ { 1 , 3 , 5 , 7 , 9 } . There arethus 25 unit squares which lie in an odd number of rectangles, so the answer is 81 − 25 = 56. 2