Q5 Matemática  (IberoAmerican 1996)

Três tokens $A$, $B$, $C$ estão, cada um em um vértice de um triângulo equilátero de lado $n$. É dividido em triângulos equiláteros de lado 1, como mostrado na figura para o caso $n=3$ Inicialmente, todas as linhas da figura são pintadas de azul. As fichas estão se movendo ao longo das linhas pintando-as de vermelho, seguindo as duas regras seguintes: (1) Primeiro $A$ se move, depois $B$ se move, e então $C$, por turnos. Em cada turno, a ficha se move exatamente sobre uma linha de um dos pequenos triângulos, de um lado ao outro. (2) A não ficha se move sobre uma linha que já está pintada de vermelho, mas pode descansar em uma extremidade de um lado que já é vermelho, mesmo que haja outra ficha esperando sua vez. Mostre que para todo inteiro positivo $n$ é possível pintar de vermelho todos os lados dos pequenos triângulos.