1
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ What picture? I see no picture... $\endgroup$
    – Xander Henderson
    Mar 29, 2020 at 0:34
  • $\begingroup$ I swear it was there when I posted my answer! I left and came back to verify! If it disappears again, the same question was asked on Quora.com, and my proof is at quora.com/… $\endgroup$
    – Darrah
    Mar 30, 2020 at 1:07
  • 1
    $\begingroup$ Those are fairly easy puzzles. In the description below, I use R, L, UL, UR to represent going one edge right, left, diagonally up to the left, and diagonally up to the right. We need to set the base case for n=1, n=2, and n=3. Here are the paths for the brush that starts in the bottom right corner; all other brushes use rotations of its path: n = 1. Path = L. n = 2. Path = L, UL, UR. n = 3. Path = L, UL, DL, UL, UR, UR. The path when n = 3 is really the same path described in the picture for the inductive case, just shorter. $\endgroup$
    – Darrah
    Apr 1, 2020 at 3:55
  • 1
    $\begingroup$ @mrlocal I don't see rigor flaws in the proposed proof; it is easy to check whether the stated claims are true or false. $\endgroup$ Apr 10, 2020 at 9:32
  • 1
    $\begingroup$ Thanks to Alex for the support. My impression is that what I have given is a rigorous proof, at least so far as a published paper would expect. For a math exercise, you could fill in details on some of the stated claims. Some mathematicians would insist that the proof be re-written so as not to rely on the picture; I am not one of those. $\endgroup$
    – Darrah
    Apr 11, 2020 at 14:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .