CEMC Pascal, 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.

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$ .

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,604 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.