Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(Replaced PNG with Asymptote)
(→‎Problem)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
How many paths from A to B consist of exactly six line
+
How many paths from <math>A</math> to <math>B</math> consist of exactly six line segments (vertical, horizontal or inclined)?
−
segments (vertical, horizontal or inclined)?
 
  
−
<asy>size(150);
+
<asy>
−
dotfactor=7;
+
for(int i = 0; i < 3; ++i){
−
pointpen=blue;
+
draw((0,i+1)--(0,i)--(4,i)--(4,i+1));
−
draw(unitsquare);
+
draw((4/3,i+1)--(4/3,i)--(8/3,i+1)--(8/3,i));
−
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((0,3)--(4,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));
+
label("$A$",(0,0),SW);
−
for(int i=0;i<4;++i)
+
label("$B$",(4,3),NE);
−
  for(int j=0;j<4;++j)
+
//Credit to chezbgone2 for the diagram</asy>
−
    dot((i/3,j/3));
 
−
MP("\mathrm{A}",D((0,0)),SW,fontsize(9)+blue);
 
−
MP("\mathrm{B}",D((1,1)),NE,fontsize(9)+blue);</asy>
 
  
 
== Solution ==
 
== Solution ==
Line 24: Line 20:
 
In total, we get <math>20 + 6 = 26</math> paths.
 
In total, we get <math>20 + 6 = 26</math> paths.
  
−
== See also ==
+
== 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]]

Latest revision as of 13:37, 20 April 2014

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1997_PMWC_Problems/Problem_I15&oldid=61646"