Competition problem — Combinatorics

Library / /169 of 220

Combinatorics Difficulty 6.6 National Olympiad Prove it Ukraine

Let $n$ be a positive integer. Equilateral triangle with the side length $n$ is divided into $n^2$ smaller equilateral triangles with the side length $1$ (Fig. 31 shows this division for $n=10$ ). Initially, one of these triangles is blue and the rest are yellow. The blue triangle is guaranteed not to have any common points with the boundary of the big triangle. It is allowed to consider any of $n^2$ equilateral triangles and change its color together with the colors of its neighbors (blue changes to yellow, yellow changes to blue). Is there any $n$ for which it is possible to make all $n^2$ equilateral triangles of the same color?

(Arsenii Nikolaiev)

Solution

Let's consider one step and assume that some triangle $a$ and his neighbors changed color on this step. Pairs that include $a$ do not influence $X$ , because if they had the same color - they will stay the same, and if they had different colors, after the recoloring they will also have different colors. Now, we point out that each of neighboring triangles
to a is always adjacent with two more small triangles. If both of them had the same color then after repainting they will increase/decrease X by $2$ . If they had the same color, then they do not change X. If it is possible to make all triangles unicolor, then initial $X = 3$ will become equal to $0$ , which contradicts the invariant.

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.