Maths Olympiad Prep

Library / /5 of 9

, 2019

Combinatorics Difficulty 5.4 AIME, harder Prove it United States

Problem:
Find all positive integers nn such that the unit segments of an n×nn \times n grid of unit squares can be partitioned into groups of three such that the segments of each group share a common vertex.

Solution

Solution:
Answer: n0,2(mod6)n \equiv 0,2(\bmod 6)
We first prove that n0,2(mod6)n \equiv 0,2(\bmod 6) is necessary for there to be such a partitioning. We break this down into proving that nn has to be even and that n0,2(mod3)n \equiv 0,2(\bmod 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 2n(n+1)2 n(n+1), has to be a multiple of three as each T-shape consists of three segments, hence either nn or n+1n+1 is a multiple of 3, implying that n0,2(mod3)n \equiv 0,2(\bmod 3).
We can then show that these two conditions is sufficient by showing that n=2n=2 and n=6n=6 works and n=k+6n=k+6 works whenever n=kn=k works. The construction for n=2n=2 is simple; just put a T-shape with the longer side on each of the four sides. For n=6n=6 and to go from n=kn=k to n=k+6n=k+6, consider the following diagram:
Figure 1
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=6n=6 can be considered as a special case where the middle square is a single point.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.