Library / /282 of 297

, 2016

Combinatorics Difficulty 4.7 AIME Find the answer Canada

Grid lines are drawn on three faces of a rectangular prism, as shown.

A squirrel walks from $P$ to $Q$ along the edges and grid lines in such a way that she is always getting closer to $Q$ and farther away from $P$ . How many different paths from $P$ to $Q$ can the squirrel take?

Pick one

Solution

We label the remaining points on the diagram as shown.

[[IMAGE0]]

There is exactly one path that the squirrel can take to get to each of $A$ , $C$ , $F$ , $B$ , $E$ , and $J$ .

For example, to get to $F$ the squirrel must walk from $P$ to $A$ to $C$ to $F$ .

The number of paths that the squirrel can take to point $D$ is 2, since there is 1 path to each of $A$ and $B$ , and to get to $D$ , the squirrel must go through exactly one of $A$ or $B$ .

Similarly, the number of paths to $G$ is the sum of the number of paths to $C$ and to $D$ (that is, $1+2=3$ ), because for the squirrel to get to $G$ , it must walk through exactly one of $C$ or $D$ .

Using this process, we add to the diagram the number of paths to reach each of $H$ , $I$ , $K$ , and $L$ .

[[IMAGE1]]

Finally, to get to $Q$ , the squirrel must go through exactly one of $H$ , $K$ , or $L$ , so the number of paths to $Q$ is $6+4+4=14$ .

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

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.