Difference between revisions of "1997 PMWC Problems/Problem I15"
I like pie (talk | contribs) m (Small edit to Asymptote code) |
m |
||
| Line 24: | Line 24: | ||
In total, we get <math>20 + 6 = 26</math> paths. | In total, we get <math>20 + 6 = 26</math> paths. | ||
| − | == See | + | == See Also == |
{{PMWC box|year=1997|num-b=I14|num-a=T1}} | {{PMWC box|year=1997|num-b=I14|num-a=T1}} | ||
[[Category:Introductory Combinatorics Problems]] | [[Category:Introductory Combinatorics Problems]] | ||
Revision as of 16:05, 15 May 2012
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]](http://latex.artofproblemsolving.com/e/2/b/e2bdd52a3db2fa22988879d1c950628d7cee5d2e.png)
Solution
- Ignoring the diagonal segments, there are
paths. - Traversing the diagonals, we quickly find that the path must run through exactly 2 diagonals. There are
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.
paths.
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 
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 | ||
