2012 AMC 10B Problem 25

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:lattice paths casework multiplication principle

Difficulty rating: 2460

Small hint:

Classify paths by which backward arrows they use

Big hint:

The no-backward-arrow case has

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

choices by column

Solution:

Classify a path by the set

S

of backward arrows it uses. If

S=\varnothing

, the path is determined by choosing one forward arrow in each column, giving

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

paths.

If

S

uses only the left backward arrow, there are

2^8

paths, and by symmetry the same for only the right backward arrow. If it uses both outer backward arrows but not the middle one, there are

2^6

paths.

If

S

uses only the middle backward arrow, there are

2^9

paths. If it uses the middle arrow and exactly one outer backward arrow, there are

2^7

paths for each choice of outer arrow. If it uses all three backward arrows, there are

2^5

paths.

The total is

2^{10}

+2\cdot2^8

+2^6

+2^9

+2\cdot2^7

+2^5=2400

.

Thus, E is the correct answer.

2012 AMC 10B Problem 25

Answer: E

Difficulty rating: 2460

Small hint:

Big hint:

Solution:

Problem 25 in other years