1997 PMWC Problems/Problem I15

Revision as of 18:16, 8 October 2007 by Azjps (talk | contribs) (sol)

Problem

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

1997 PMWC-I15.png

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