# BMO1 2005/06 Question 4 Combinatorics Problem

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.

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.