HMMT 十一月 2018 · 团队赛 · 第 7 题

HMMT November 2018 — Team Round — Problem 7

[ 50 ] A 5 × 5 grid of squares is filled with integers. Call a rectangle corner-odd if its sides are grid lines and the sum of the integers in its four corners is an odd number. What is the maximum possible number of corner-odd rectangles within the grid? Note: A rectangle must have four distinct corners to be considered corner-odd ; i.e. no 1 × k rectangle can be corner-odd for any positive integer k .

解析

[ 50 ] A 5 × 5 grid of squares is filled with integers. Call a rectangle corner-odd if its sides are grid lines and the sum of the integers in its four corners is an odd number. What is the maximum possible number of corner-odd rectangles within the grid? Note: A rectangle must have four distinct corners to be considered corner-odd ; i.e. no 1 × k rectangle can be corner-odd for any positive integer k . Proposed by: Henrik Boecken Answer: 60 Consider any two rows and the five numbers obtained by adding the two numbers which share a given column. Suppose a of these are odd and b of these are even. The number of corner-odd rectangles with their sides contained in these two rows is ab . Since a + b = 5, we have ab ≤ 6. Therefore every pair of rows contains at most 6 corner-odd rectangles. ( ) 5 There are = 10 pairs of rows, so there are at most 60 corner-odd rectangles. Equality holds when 2 we place 1 along one diagonal and 0 everywhere else.