
4. A person moves in the $x-y$ plane moving along points with integer co-ordinates $x$ and $y$ only. When she is at point $(x, y)$, she takes a step based on the following rules:

(a) if $x+y$ is even she moves to either $(x+1, y)$ or $(x+1, y+1)$;

(b) if $x+y$ is odd she moves to either $(x, y+1)$ or $(x+1, y+1)$.

How many distinct paths can she take to go from $(0,0)$ to $(8,8)$ given that she took exactly three steps to the right $((x, y)$ to $(x+1, y))$ ?


## Solution.

We note that she must also take three up steps and five diagonal steps. Now, a step to the right or an upstep changes the parity of the co-ordinate sum, and a diagonal step does not change it. Therefore, between two right steps there must be an upstep and similarly between two upsteps there must be a right step. We may, therefore write

$$
H V H V H V
$$

The diagonal steps may be distributed in any fashion before, in between and after the HV sequence. The required number is nothing but the number of ways of distributing 5 identical objects into 7 distinct boxes and is equal to $\binom{11}{6}$.
