HMMT 二月 2002 · ADV 赛 · 第 8 题

HMMT February 2002 — ADV Round — Problem 8

Given a 9 × 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?

解析

Given a 9 × 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? Solution: 56 . Consider the rectangles which contain the square in the i th row and j th column. There are i possible positions for the upper edge of such a rectangle, 10 − i for the lower 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 are thus 25 unit squares which lie in an odd number of rectangles, so the answer is 81 − 25 = 56. 2