返回题库

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

HMMT February 2019 — Team Round — Problem 5

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 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.
    °
解析

英文解析

  1. [ 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.
    °