Show for all positive integers, it is possible to paint all of the segments red.

Question

Three counters, A, B, C are placed at the corners of an equilateral triangle of side n. The triangle is divided into triangles of side length 1. Initially all lines of the figure are painted blue. The counters move along the lines, painting their paths red , according to the following rules:

• First A moves, then B, then C, then A, and so on in succession.
• On each turn, each counter moves the full length of a side of one of the short triangles.
• No counter may retrace a segment already painted red, though it can stop on a red vertex, even if another counter is already there.

Show that for all integers n > $0$ it is possible to paint all of the segments red in this fashion.

I have a feeling we use induction method to show this. Im not quite sure where to start though. I have to figure out how to prove this rigorously. From the help of few kind people, i know there must be three base cases for n=1 n=2 and n=3. Im just not sure how to prove this without giving any drawings.

Answer 1

Maybe this is a start:

Suppose you can partition the edges of the graph into three disjoint sets ($A, B, C$) such that

• the corresponding subgraphs $G_A, G_B, G_C$ are connected
• $A$, $B$, $C$ have equal cardinality
• Either one of the three corners of the triangle have degree $2$ for $G_A$, one has degree $2$ for $G_B$, and one has degree $2$ for $G_C$, or one has degrees $1,1,0$ for $G_A, G_B, G_C$ respectively, one has $0,1,1$, and one has $1,0,1$.
• All other vertices have even degrees for $G_A$, $G_B$ and $G_C$.

Then by each counter can traverse an Eulerian path in the edges for its corresponding subgraph, either starting and ending at the same corner or starting at one and ending at another.

Answer 2

In the picture below, the inner red triangle shows the area where we’ll be doing induction. We proceed as follows:

1. The paintbrush from the lower right corner follows the path shown in blue, ending at the heavy black dot, which is a corner of the induction triangle; the other two paintbrushes follow symmetric paths.
2. We use induction on the inner triangle, paint it completely, and all three brushes end up back at corners of the red triangle (although not necessarily at the corners from which they began). (Note: You can assert that they end at those corners either by adding that to the induction hypothesis or by using Euler’s theorem.)
3. The paint brush that ended at the heavy black dot now follows the green path, ending at the topmost vertex; the other two brushes follow symmetric patterns. The triangle is now painted as requested: Every edge is painted; no edge is painted twice.

I’ll note that you have to establish three base cases, for $n=1$, $n=2$, and $n=3$. Those are straight-forward. The path taken by one brush