MathDB

Square table and a pawn

Source: Bulgarian IMO TST 2008, Day 1, Problem 1

July 8, 2013

inductioncombinatorics proposedcombinatoricsgraph theoryHamiltonian pathChessboard

Problem Statement

Let

n

be a positive integer. There is a pawn in one of the cells of an

n\times n

table. The pawn moves from an arbitrary cell of the

k

th column,

k \in \{1,2, \cdots, n \}

, to an arbitrary cell in the

k

th row. Prove that there exists a sequence of

n^{2}

moves such that the pawn goes through every cell of the table and finishes in the starting cell.