2012 AMC 12B Problem 22

Question

A bug travels from

A

to

B

along the segments in the hexagonal lattice pictured below. The segments marked with an arrow can be traveled only in the direction of the arrow, and the bug never travels the same segment more than once. How many different paths are there?

2112

2304

2368

2384

2400

Answer: E

Concepts:casework multiplication principle

Difficulty rating: 2270

Small hint:

There are three left-pointing “back” segments; split into cases by which subset of them the path uses

Big hint:

With no back segment used, the path picks one forward segment per column, giving

2\cdot2\cdot4\cdot4\cdot4\cdot2\cdot2=2^{10}

Solution:

Label the seven columns of forward (rightward) segments; a path with no back segment simply chooses one forward segment in each column. The numbers of choices are

2,2,4,4,4,2,2,

giving

2^{10}

paths.

Let

s_1,s_2,s_3

be the three left-pointing back segments (in columns

2,4,6

). Analyzing which columns become forced once a back segment is traversed gives

2^8

paths for each of

\{s_1\}

and

\{s_3\},

2^6

for

\{s_1,s_3\},

2^9

for

\{s_2\},

2^7

for each of

\{s_1,s_2\}

and

\{s_2,s_3\},

and

2^5

for

\{s_1,s_2,s_3\}.

Adding,

\begin{aligned} &2^{10}+2\cdot2^8+2^6 \\ &\quad {}+2^9+2\cdot2^7+2^5=2400. \end{aligned}

Thus, the correct answer is E.