Problem

Source: Mumbai Region RMO 2014 Problem 4

Tags: analytic geometry, combinatorics unsolved, combinatorics



A person moves in the $x-y$ plane moving along points with integer co-ordinates $x$ and $y$ only. When she is at a 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))$?