Maths Olympiad Prep

Library / /16 of 19

Combinatorics Difficulty 7.0 National olympiad Prove it Romania

The sides of an equilateral triangle are divided into nn equal parts by n1n-1 points on each side. Through these points one draws parallel lines to the sides of the triangle. Thus, the initial triangle is divided into n2n^2 equal equilateral triangles. In every vertex of such a triangle there is a beetle. The beetles start crawling simultaneously, with equal speed, along the sides of the small triangles. When they reach a vertex, the beetles change the direction of their movement by 6060^\circ or by 120120^\circ.

a) Prove that, if n7n \ge 7, the beetles can move indefinitely on the sides of the small triangles without two beetles ever meeting in a vertex of a small triangle.

b) Determine all the values of n1n \ge 1 for which the beetles can move along the sides of the small triangles without meeting in their vertices.

Solution

It is easy to see (by induction or otherwise) that, for n3n \ge 3 odd, the set of the vertices of the small triangle can be partitioned into groups of 3 and 4 vertices that form either an equilateral triangle or a rhombus formed by gluing together two such triangles. On each of these polygonal lines, the beetles can move in a circuit, changing at each step their direction.

Alternatively, one can provide a direct example in this case: we call a strip an isosceles trapezoid whose legs are part of the original triangle's sides and whose bases are horizontal and we label the strips from top to bottom, strip number kk consisting of 2k12k-1 small equilateral triangles. Then we can choose the triangles and the rhombi as follows: on the strip kk with kk odd we place a triangle, then k1k-1 rhombi. An example for n=7n=7 is shown below:
Figure 1

Figure 1

In general, if for a given nn the beetles can move without meeting, then they can move indefinitely for n+2n+2 as well. For n=1n=1 and n=8n=8 one can give examples. A possible example for n=8n=8:

Figure 2

The inductive step for the case when nn is even: if the triangle whose sides have been divided into n2n \ge 2 equal parts can be traveled by the beetles without intersecting, then so can the triangle whose sides have been divided into n+2n+2 equal parts: it is enough to split the triangles with side length n+2n+2 into an equilateral triangle of side length nn plus two strips, of which the lower one can be partitioned according to the model exemplified below for n=8n=8:
Figure 3

Why can the beetles not move indefinitely without meeting in the case when n=6n=6?
We color red all the vertices situated on odd position in rows with an odd number, the numbering starting from top to bottom, as in the following figure:

Figure 4

We color the remaining points blue. A beetle can not get in one step from a red vertex to another red one, nor can it achieve this in two steps because it needs to change direction after the first step. After two steps, those 10 beetles initially positioned in a red vertex need to be in blue vertices, but so do the 10 beetles that were in red vertices after the first step. But there are only 18 vertices to accommodate these 20 beetles, so some beetles need to meet after two steps.
If for n=2n=2 the beetles would be able to move without meeting, from the inductive step it would follow that the same would be true for n=4n=4 and then also for n=6n=6, which is not happening.

In conclusion, the beetles can move indefinitely without ever meeting if and only if nN{2,4,6}n \in \mathbb{N} \setminus \{2, 4, 6\}.

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 and solution reproduced as published; topic and difficulty added by this site.