1997 PMWC Problems/Problem I15

Problem

How many paths from $A$ to $B$ consist of exactly six line segments (vertical, horizontal or inclined)?

[asy] for(int i = 0; i < 3; ++i){ draw((0,i+1)--(0,i)--(4,i)--(4,i+1)); draw((4/3,i+1)--(4/3,i)--(8/3,i+1)--(8/3,i)); } draw((0,3)--(4,3)); label("$A$",(0,0),SW); label("$B$",(4,3),NE); //Credit to chezbgone2 for the diagram[/asy]

Solution

Casework:

  • Ignoring the diagonal segments, there are $\frac{6!}{3!3!} = 20$ paths.
  • Traversing the diagonals, we quickly find that the path must run through exactly 2 diagonals. There are ${3\choose2} = 3$ pairs of diagonals through which this is possible; quick counting shows us that each pair of diagonals yields 2 paths. So there are 6 more cases here.

In total, we get $20 + 6 = 26$ paths.

See Also

1997 PMWC (Problems)
Preceded by
Problem I14
Followed by
Problem T1
I: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
T: 1 2 3 4 5 6 7 8 9 10