IMO 1999 SL C1

Origin: IND | Category: Combinatorics

Problem

Let n \geq1 be an integer. A path from (0, 0) to (n, n) in the xy plane is a chain of consecutive unit moves either to the right (move denoted by E) or upwards (move denoted by N), all the moves being made inside the half-plane x \geqy. A step in a path is the occurrence of two consecutive moves of the form EN. Show that the number of paths from (0, 0) to (n, n) that contain exactly s steps (n \geqs \geq1) is s n −1 s −1  n s −1  .

Solution

Let us call f(n, s) the number of paths from (0, 0) to (n, n) that contain exactly s steps. Evidently, for all n we have f(n, 1) = f(2, 2) = 1, in accordance with the formula. Let us thus assume inductively for a given n > 2 that for all s we have f(n, s) = 1 s
n−1 s−1 
n s−1  . We shall prove that the given formula holds also for all f(n + 1, s), where s \geq2. We say that an (n+ 1, s)- or (n+ 1, s+ 1)-path is related to a given (n, s)- path if it is obtained from the given path by inserting a step EN between two moves or at the beginning or the end of the path. We note that by inserting the step between two moves that form a step one obtains an (n + 1, s)-path; in all other cases one obtains an (n + 1, s + 1)-path. For each (n, s)-path there are exactly 2n + 1 −s related (n + 1, s + 1)-paths, and for each (n, s + 1)-path there are s + 1 related (n + 1, s + 1)-paths. Also, each (n + 1, s + 1)-path is related to exactly s + 1 different (n, s)- or (n, s + 1)-paths. Thus: (s + 1)f(n + 1, s + 1) = (2n + 1 −s)f(n, s) + (s + 1)f(n, s + 1) = 2n + 1 −s s n −1 s −1  n s −1  + n −1 s n s 

n s n + 1 s  , i.e., f(n + 1, s + 1) = s+1
n s 
n+1 s  . This completes the proof.