HMMT 二月 2019 · 团队赛 · 第 5 题

HMMT February 2019 — Team Round — Problem 5

[ 40 ] Find all positive integers n such that the unit segments of an n × n grid of unit squares can be partitioned into groups of three such that the segments of each group share a common vertex. ◦

解析

[ 40 ] Find all positive integers n such that the unit segments of an n × n grid of unit squares can be partitioned into groups of three such that the segments of each group share a common vertex. Proposed by: Yuan Yao Answer: n ≡ 0 , 2 (mod 6) We first prove that n ≡ 0 , 2 (mod 6) is necessary for there to be such a partitioning. We break this down into proving that n has to be even and that n ≡ 0 , 2 (mod 3). The only way a segment on a side of the square can be part of such a T-shape is as one of the two consecutive segments along the longer side of the T-shape, so they must come in pairs and therefore, the length of each side has to be even. On the other hand, the total number of segments, which is 2 n ( n + 1), has to be a multiple of three as each T-shape consists of three segments, hence either n or n + 1 is a multiple of 3, implying that n ≡ 0 , 2 (mod 3). We can then show that these two conditions is sufficient by showing that n = 2 and n = 6 works and n = k + 6 works whenever n = k works. The construction for n = 2 is simple; just put a T-shape with the longer side on each of the four sides. For n = 6 and to go from n = k to n = k + 6, consider the following diagram: There are two main parts – the cycle of stacks of T’s in all four orientation (see the red, blue, yellow, and green stacks), and the border (seen here by the cyan, brown, and black T-shapes). The case n = 6 can be considered as a special case where the middle square is a single point. ◦