MathDB
Counting monotonous paths in $n\times n$ square

Source: Tuymaada 2021 Senior P4

July 28, 2021
counting problemcombinatorics

Problem Statement

An n×nn\times n square (nn is a positive integer) consists of n2n^2 unit squares.A \emph{monotonous path} in this square is a path of length 2n2n beginning in the left lower corner of the square,ending in its right upper corner and going along the sides of unit squares. For each kk, 0≤k≤2n−10\leq k\leq 2n-1, let SkS_k be the set of all the monotonous paths such that the number of unit squares lying below the path leaves remainder kk upon division by 2n−12n-1.Prove that all SkS_k contain equal number of elements.
Back to ProblemsView on AoPS