### 64th Putnam 2003

Problem A5

An n-path is a lattice path starting at (0,0) made up of n upsteps (x,y) → (x+1,y+1) and n downsteps (x,y) → (x-1,y-1). A downramp of length m is an upstep followed by m downsteps ending on the line y = 0. Find a bijection between the (n-1)-paths and the n-paths which have no downramps of even length.

Solution

Let S be the set of n-1 paths and T the set of n-paths without even downramps. Define u: S → T as follows. If the path has no even downramps, then add an upstep followed by a downstep at the start of the path. Otherwise add an upstep at the start and a downstep after the last even downramp. The new path is obviously an n-path and has no downramps until what was the last even downramp, but is now odd. Hence all its downramps are odd and it belongs to T.

Define d: T → S as follows. Remove an upstep from the start and remove a downstep from the first downramp. The result is obviously in S. A little thought shows that ud and du are both identity maps. Hence u and d are both bijections.