Competition problem — Combinatorics

Library / /134 of 377

Combinatorics Difficulty 4.9 AIME Find the answer United States

Problem:

Bessie the cow is trying to navigate her way through a field. She can travel only from lattice point to adjacent lattice point, can turn only at lattice points, and can travel only to the east or north. (A lattice point is a point whose coordinates are both integers.) $(0,0)$ is the southwest corner of the field. $(5,5)$ is the northeast corner of the field. Due to large rocks, Bessie is unable to walk on the points $(1,1)$ , $(2,3)$ , or $(3,2)$ . How many ways are there for Bessie to travel from $(0,0)$ to $(5,5)$ under these constraints?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution: 32
In the figure, each point is labeled with the number of ways to reach that point. The numbers are successively computed as follows: The point $(0,0)$ can trivially be reached in 1 way. When Bessie reaches any subsequent point $(x, y)$ (other than a rock), she can arrive either via a northward or an eastward step, so the number of ways she can reach that point equals the number of ways of reaching $(x-1, y)$ plus the number of ways of reaching $(x, y-1)$ . By iterating this calculation, we eventually find that $(5,5)$ can be reached in 32 ways.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.