On an infinite square grid we place finitely many cars, which each occupy a single cell and face in one of the four cardinal directions. Cars may never occupy the same cell. It is given that the cell immediately in front of each car is empty, and moreover no two cars face towards each other (no right-facing car is to the left of a left-facing car within a row, etc.). In a move, one chooses a car and shifts it one cell forward to a vacant cell. Prove that there exists an infinite sequence of valid moves using each car infinitely many times.
Solution
To do so, we outline a five-stage plan for the cars.
1. All vertical cars in a green cell may advance one cell into a red cell (or exit altogether), by the given condition. (This is the only place where the hypothesis about empty space is used!)
2. All horizontal cars on green cells may exit , as no vertical cars occupy green cells.
3. All vertical cars in a red cell may advance one cell into a green cell (or exit altogether), as all green cells are empty.
4. All horizontal cars within red cells may exit , as no vertical car occupy red cells.
5. The remaining cars exit , as they are all vertical. The solution is complete.
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.