MathDB
IMO ShortList 1999, combinatorics problem 1

Source: IMO ShortList 1999, combinatorics problem 1

November 14, 2004
binomial coefficientsalgebracountingcombinatoricsIMO Shortlist

Problem Statement

Let n≥1n \geq 1 be an integer. A path from (0,0)(0,0) to (n,n)(n,n) in the xyxy plane is a chain of consecutive unit moves either to the right (move denoted by EE) or upwards (move denoted by NN), all the moves being made inside the half-plane x≥yx \geq y. A step in a path is the occurence of two consecutive moves of the form ENEN. Show that the number of paths from (0,0)(0,0) to (n,n)(n,n) that contain exactly ss steps (n≥s≥1)(n \geq s \geq 1) is 1s(n−1s−1)(ns−1).\frac{1}{s} \binom{n-1}{s-1} \binom{n}{s-1}.
Back to ProblemsView on AoPS