In the 4x4 square shown below, you have to get from X to Y moving only along black lines.

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.


Correctly solved by:

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