Grid: Avoid Trap

Consider an 8 $\times$ 8 grid from $$(0,0)$$ to $$(8,8)$$ . Each step moves one unit right (R) or one unit up (U). We wish to avoid any point with odd $$x$$ and odd $$y$$ -coordinates, e.g. $(1,1), (1,3), (3,5), \dots$ . How many ways are there to reach $$(8,8)$$ without ever landing on one of these “trap” points?

Answer

Starting at $$(0,0)$$ (both coordinates even), we note that moving $\text{R}$ then $\text{U}$ (or $\text{U}$ then $\text{R}$ ) in consecutive steps would produce a point $(\text{odd}, \text{odd})$ , which is forbidden. Therefore, the only way to avoid trap points is to move in “pairs” of the same direction: either $\text{RR}$ or $\text{UU}$ .

Since we must reach $$(8,8)$$ , we need exactly 8 total $\text{R}$ steps and 8 total $\text{U}$ steps. Group these 16 steps into 8 pairs. Each pair is either $\text{RR}$ (2 $\text{R}$ steps) or $\text{UU}$ (2 $\text{U}$ steps). We require exactly 4 $\text{RR}$ pairs (making 8 $\text{R}$ steps) and 4 $\text{UU}$ pairs (making 8 $\text{U}$ steps). Thus, we are simply choosing which 4 out of the 8 pairs are $\text{UU}$ . This can be done in

\binom{8}{4} \;=\; 70

ways. Hence, there are $\boxed{70}$ valid paths that avoid all trap points.