1
$\begingroup$

The equilateral triangle $ABC$ has sides of integer length $N$. The triangle is completely divided (by drawing lines parallel to the sides of the triangle) into equilateral triangular cells of side length $1$.

A continuous route is chosen, starting inside the cell with vertex $A$ and always crossing from one cell to another through an edge shared by the two cells. No cell is visited more than once. Find, with proof, the greatest number of cells which can be visited.

I think I've managed to prove that the number of cells in the triangle is equal to $N^2$, however I'm not sure how rigorous this was. I've spotted that the correct answer seems to be $N^2-N+1$, though I'm not able to prove it. I've been looking at how certain cells become dead ends, but as you go further down things become more complicated and there is no clear proof in sight.

Can anyone come up with a hint or full proof. Thanks in advance.

$\endgroup$
4
$\begingroup$

Orient the triangle so that it is pointing upwards, with $A$ in the top corner. Paint each upwards-pointing triangular cell white and each downward-pointing cell black. Then each move takes you from a white cell to a black cell or the other way around. There are $\frac{N^2 + N}{2}$ white cells, and $\frac{N^2 - N}{2}$ black cells.

You can at most keep moving until you've been through all the black cells, and one more white cell than black cells (since you start in a white cell). By then you've been through $$ \frac{N^2 - N}{2} + \left(\frac{N^2 - N}{2} + 1\right) = N^2 - N + 1 $$ cells, so whatever you do, you can't do better than this. Note that we haven't proven that $N^2 - N + 1$ is possible yet, that's in the next paragraph.

Now that we know the theoretical maximum, it's just a matter of noting that going through the rows one-by-one, zig-zagging back and forth, skipping the first white cell in each row will take you through all the black cells, and have you end up in a white cell (either $B$ or $C$). We've shown that it cannot be done better, so we're done.

$\endgroup$
  • $\begingroup$ Thanks. After posting the question I managed to realise there always was a way of reaching that many cells using the technique you described, but still couldn't prove it couldn't be more. After seeing your solution I think I have seen the strategy of labelling cells different colours before (in a different scenario), but it didn't spring to mind, so I appreciate the help. $\endgroup$ – MadChickenMan Jun 14 '15 at 22:01
  • $\begingroup$ @MadChickenMan Colouring proofs can be quite elegant at times. It often pops up in connection to parity. In this case, every other move takes you to a black cell, the rest take you to a white one. In other cases, you might be asked to cover a triangular or rectangular board with specific pieces, and you can do a colouring that will make, for instance, every piece cover an even number of whites, or equally many white and black cells. Some times you color every other cell, some times you color regions. $\endgroup$ – Arthur Jun 14 '15 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.