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 bepartitioned 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 bepartitioned 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 thisdown 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 twoconsecutive 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 orn + 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 andn = 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.
°