1997 PMWC Problems/Problem I15

Problem

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

$[asy]size(150); dotfactor=7; pointpen=black; draw(unitsquare); draw((1/3,0)--(1/3,1));draw((2/3,0)--(2/3,1)); draw((0,1/3)--(1,1/3));draw((0,2/3)--(1,2/3)); draw((1/3,0)--(2/3,1/3));draw((1/3,1/3)--(2/3,2/3));draw((1/3,2/3)--(2/3,1)); for(int i=0;i<4;++i) for(int j=0;j<4;++j) dot((i/3,j/3)); MP("\mathrm{A}",D((0,0)),SW,fontsize(9)); MP("\mathrm{B}",D((1,1)),NE,fontsize(9));[/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.

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

Page

Toolbox

Search

1997 PMWC Problems/Problem I15

Problem

Solution

See also