Difference between revisions of "1997 PMWC Problems/Problem I15"

Revision as of 14:07, 16 April 2008

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.

@@ Line 5: / Line 5: @@
 <asy>size(150);
 dotfactor=7;
-pointpen=blue;
+pointpen=black;
 draw(unitsquare);
 draw((1/3,0)--(1/3,1));draw((2/3,0)--(2/3,1));
@@ Line 13: / Line 13: @@
    for(int j=0;j<4;++j)
      dot((i/3,j/3));
-MP("\mathrm{A}",D((0,0)),SW,fontsize(9)+blue);
+MP("\mathrm{A}",D((0,0)),SW,fontsize(9));
-MP("\mathrm{B}",D((1,1)),NE,fontsize(9)+blue);</asy>
+MP("\mathrm{B}",D((1,1)),NE,fontsize(9));</asy>
 == Solution ==

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

Difference between revisions of "1997 PMWC Problems/Problem I15"

Revision as of 14:07, 16 April 2008

Problem

Solution

See also