Learn / Library / Combinatorics

Routes around a hole

CombinatoricsMedium

A robot moves on a grid from $(0, 0)$ to $(5, 5)$ , and each move goes $1$ unit east or $1$ unit north. The point $(2, 2)$ is a hole, and the robot must never step on it. How many routes avoid the hole?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Count all routes, then remove the ones that pass through the bad point.

Solution

Without restrictions there are $(5 10) = 252$ routes.
A route that steps on the hole splits into a part from $(0, 0)$ to $(2, 2)$ and a part from $(2, 2)$ to $(5, 5)$ .
The first part has $(2 4) = 6$ routes and the second has $(3 6) = 20$ routes, so $6 \times 20 = 120$ routes use the hole.
A route visits the hole at most once, so nothing is counted twice, and the answer is $252 - 120 = 132$ .

Answer: $132$

Next question Back to the library