Answer to March 29, 2004 Problem |
---|
Shortest Distance Problem |
---|
How many different shortest routes are there from X to Y?
|
---|
Solution to the Problem:
The number of shortest paths is 34.
We first note that a shortest path must always move to the right and up,
never left or down. We begin in the upper-right corner and proceed back to the
lower-left corner, counting the number of paths from the point in question to the
upper-right corner. There is one shortest "path" from the upper right corner to itself.
Now any shortest path starting at a point must first move up or right if possible.
The number of such paths will be the sum of the number of such paths starting at the
point above it (if there is one) and the number of such paths starting at the point to
the right of it (if there is one). As we go from upper-right to lower-left writing
the sum of the numbers above and to the right, we obtain the diagram below.
Therefore the total number of paths we seek is 34.
Yes, I have used a variation of this problem before. Pascal's Triangle is visible in the
upper right hand corner. If I had inserted the four connecting lines in the middle, it
would have been clearer that Pascal's Triangle was at work here.
|
1. John Funk | Ventura, California |
2. Akash Patel | Columbus, Georgia |
3. Richard Johnson | La Jolla, California |
4. Walt Arrison | Philadelphia, Pennsylvania |
5. Jeffrey Gaither | Winchester, Virginia |
6. David & Judy Dixon | Bennettsville, South Carolina |
7. Viktor Bergqvist | Tullängsskolan , Sweden |
8. James Alarie | University of Michigan -- Flint Flint, Michigan |
9. Larry Schwartz | Trumbull, Connecticut |
10. Jason Storer | Winchester, Virginia |
11. Josh Feingold | Winchester, Virginia |
12. David Wong | Winchester, Virginia |
13. Kristofer Friman | Tullängsskolan, Sweden |
14. Chris Maggiolo | Harrisonburg, Virginia |
15. Alex Truong | Harrisonburg, Virginia |
16. Kirby Welsko | Harrisonburg, Virginia |
17. Bella Patel | Harrisonburg, Virginia |
18. Helna Patel | Harrisonburg, Virginia |