Competition problem — Combinatorics

Library / /5 of 16

Combinatorics Difficulty 5.5 AIME, harder Prove it Brazil

An ant crawls in plane as follows: it initially crawls 1 cm in either direction. Then, after each step, it turns $60^\circ$ 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 $O$ 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 $O$ 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 $2008 = 6 \cdot 334 + 4 = 6 \cdot 332 + 2 \cdot 10$ , the ant can do 332 6-step round paths and 2 10-step round paths, coming back to $O$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.