Browse · MathNet
PrintXXXI Brazilian Math Olympiad
Brazil counting and probability
Problem
An ant crawls in plane as follows: it initially crawls 1 cm in either direction. Then, after each step, it turns to the left or to the right and crawls 1 cm in the new direction. 
Is it possible for it to return to its starting point in (a) 2008 steps? (b) 2009 steps?
Solution
Let be the starting point of the ant. Then the ant will walk on the following hexagonal lattice: Color the vertices in the lattice alternatively in black and white, as shown in the diagram. Then each step leads the ant from a black point to a white point or vice-versa. Hence the ant can only come back to after an even number of steps, and then the answer to (b) is no.
The ant can do 6-step round paths (a regular hexagon) and 10-step round paths (a non-convex decagon obtained by joining two regular hexagons by a common side). Since , the ant can do 332 6-step round paths and 2 10-step round paths, coming back to .
The ant can do 6-step round paths (a regular hexagon) and 10-step round paths (a non-convex decagon obtained by joining two regular hexagons by a common side). Since , the ant can do 332 6-step round paths and 2 10-step round paths, coming back to .
Final answer
a) Yes. b) No.
Techniques
Coloring schemes, extremal argumentsInvariants / monovariants