MathDB
Thesus wanders the plane

Source: HMMT Invitational Contest 2016, Problem 1

April 22, 2016
combinatoricslattice pathsHMMTHMIC

Problem Statement

Theseus starts at the point (0,0)(0, 0) in the plane. If Theseus is standing at the point (x,y)(x, y) in the plane, he can step one unit to the north to point (x,y+1)(x, y+1), one unit to the west to point (x−1,y)(x-1, y), one unit to the south to point (x,y−1)(x, y-1), or one unit to the east to point (x+1,y)(x+1, y). After a sequence of more than two such moves, starting with a step one unit to the south (to point (0,−1)(0, -1)), Theseus finds himself back at the point (0,0)(0, 0). He never visited any point other than (0,0)(0, 0) more than once, and never visited the point (0,0)(0, 0) except at the start and end of this sequence of moves.
Let XX be the number of times that Theseus took a step one unit to the north, and then a step one unit to the west immediately afterward. Let YY be the number of times that Theseus took a step one unit to the west, and then a step one unit to the north immediately afterward. Prove that ∣X−Y∣=1|X - Y| = 1.
Mitchell Lee
Back to ProblemsView on AoPS