An equilateral triangle of side n is divided into n2 equilateral triangles of side 1 by lines parallel to the sides. Initially, all the sides of all the small triangles are painted blue. Three coins A, B, C are placed at vertices of the small triangles. Each coin in turn is moved a distance 1 along a blue side to an adjacent vertex. The side it moves along is painted red, so once a coin has moved along a side, the side cannot be used again. More than one coin is allowed to occupy the same vertex. The coins are moved repeatedly in the order A, B, C, A, B, C, ... . Show that it is possible to paint all the sides red in this way.
Solution
We use induction. It is obvious for n = 1 and 2 - see diagram above. Note that A, B, C start and end at vertices of the large triangle.
Now assume that for n we can find a solution with A, B, C starting and ending at the vertices of the large triangle. Take n+1. We start with the paths shown which bring A, B, C to A', B', C' at the vertices of a triangle side n-1. Now by induction we can continue the paths so that we bring A, B, C, back to the vertices of that triangle after tracing out all its edges. Finally, note that for each of the points A', B', C' there is a path length 2 over untraced segments to a vertex of the large triangle. So we get a solution for n+1 and hence for all n.
© John Scholes
jscholes@kalva.demon.co.uk
22 Oct 2000