Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

counting and probability senior

Problem

Moving only south and east along the line segments, how many paths are there from to ?
problem
Solution
First, put the two missing segments in and count the number of paths from to on the complete grid. Each path from to consists of a sequence of 12 steps, three of which are ``down'' and nine of which are ``right.'' There are ways to arrange 3 D's and 9 R's, so there are 220 paths from to .

Now we will count the number of paths that go through one of the forbidden segments. No path goes through both of them, so we may count the number of paths that go through each segment and sum the results. Define and as shown in the figure. There are 5 ways to get from to and 6 ways to get from to . So there are ways to get from to through the first forbidden segment. Similarly, there are 30 ways to get from to through the second forbidden segment. So the total number of paths from to on the original grid is .

Final answer
160