MathDB

2

Part of 2018 OMMock - Mexico National Olympiad Mock Exam

Problems(1)

Minimum number of changes of direction

Source: Mexico National Olympiad Mock Exam 2018 Problem 2

11/6/2018
An equilateral triangle of side nn has been divided into little equilateral triangles of side 11 in the usual way. We draw a path over the segments of this triangulation, in such a way that it visits exactly once each one of the (n+1)(n+2)2\frac{(n+1)(n+2)}{2} vertices. What is the minimum number of times the path can change its direction?
The figure below shows a valid path on a triangular board of side 44, with exactly 99 changes of direction.
[asy] unitsize(30); pair h = (1, 0); pair v = dir(60); pair d = dir(120); for(int i = 0; i < 4; ++i) { draw(i*v -- i*v + (4 - i)*h); draw(i*h -- i*h + (4 - i)*v); draw((i + 1)*h -- (i + 1)*h + (i + 1)*d); }
draw(h + v -- v -- (0, 0) -- 2*h -- 2*h + v -- h + 2*v -- 2*v -- 4*v -- 3*h + v -- 3*h -- 4*h, linewidth(2)); draw(3*h -- 4*h, EndArrow); fill(circle(h + v, 0.1));
[/asy]
Proposed by Oriol Solé
combinatoricsboardpath