HMMT 二月 2016 · 团队赛 · 第 4 题

HMMT February 2016 — Team Round — Problem 4

[ 30 ] Let n > 1 be an odd integer. On an n × n chessboard the center square and four corners are 1 2 2 deleted. We wish to group the remaining n − 5 squares into ( n − 5) pairs, such that the two squares 2 in each pair intersect at exactly one point (i.e. they are diagonally adjacent, sharing a single corner). For which odd integers n > 1 is this possible? 2 3

解析

[ 30 ] Let n > 1 be an odd integer. On an n × n chessboard the center square and four corners are 1 2 2 deleted. We wish to group the remaining n − 5 squares into ( n − 5) pairs, such that the two squares 2 in each pair intersect at exactly one point (i.e. they are diagonally adjacent, sharing a single corner). For which odd integers n > 1 is this possible? Proposed by: Evan Chen Answer: 3,5 Constructions for n = 3 and n = 5 are easy. For n > 5, color the odd rows black and the even rows white. If the squares can be paired in the way desired, each pair we choose must have one black cell and one white cell, so the numbers of black cells and white cells are the same. The number of black n +1 n +1 cells is n − 4 or n − 5 depending on whether the removed center cell is in an odd row. The 2 2 n − 1 n − 1 number of white cells is n or n − 1. But 2 2 ( ) n + 1 n − 1 n − 5 − n = n − 5 2 2 so for n > 5 this pairing is impossible. Thus the answer is n = 3 and n = 5. 2 3