A map of downtown Fort Collins, Colorado is shown below. Some students at Fort Collins High School, which is labeled A in the map below, wish to visit their friends at Poudre High School, labeled C. Using only the main roads shown (notice that Overland Trail ends at Drake and that Laporte ends at College Ave.), and always traveling North and West, how many different routes are possible to get from Fort Collins High to Poudre High? How many of the paths will take them by the other high school in the city, Rocky Mountain High (labeled B)? | | | | | | Laporte C---+---+---+ | | N | | | | | | ^ Mulberry +---+---+---+---+---+ | | | | | | | W <--+--> E Prospect +---+---+---+---+---+ | | | | | | | ! Drake +---+---B---+---+---+ S | | | | | Horsetooth ----+---+---+---+---A | | | | | O T S C L T v a h o e i e f i l M m r t e l a b l l e Y e a H d g r n i s e A l d l v i i A e n T v n e r e u a n e i u l e
Solution:
The answer is 120 different ways to get from Fort
Collins High to Poudre High. Forty of these
paths take them by Rocky Mountain High.
Using a table similar to Pascal's triangle,
the numbers in the following table show how many
different ways you can get to a particular corner.
Remember, you can only travel north and west.
In each block or square, you would add the top
right hand corner number and the bottom left hand
corner number to get the number for the top left
hand corner of that square.
| | | | | | Laporte 120-65--30--10 | | N | | | | | | ^ Mulberry 55--35--20--10---4---1 | | | | | | | W <--+--> E Prospect 20--15--10---6---3---1 | | | | | | | ! Drake 5---5---4---3---2---1 S | | | | | Horsetooth ----1---1---1---1---1 | | | | | O T S C L T v a h o e i e f i l M m r t e l a b l l e Y e a H d g r n i s e A l d l v i i A e n T v n e r e u a n e i u l e The following map shows how many of the 120 routes above go past Rocky Mountain High (near the corner of Shields and Drake). The zeroes indicate that you can not pass through that corner and also pass by Rocky Mountain High going North and West: | | | | | | Laporte 40--16---4---0 | | N | | | | | | ^ Mulberry 24--12---4---0---0---0 | | | | | | | W <--+--> E Prospect 12---8---4---0---0---0 | | | | | | | ! Drake 4---4---4---3---2---1 S | | | | | Horsetooth ----0---1---1---1---1 | | | | | O T S C L T v a h o e i e f i l M m r t e l a b l l e Y e a H d g r n i s e A l d l v i i A e n T v n e r e u a n e i u l e
Correctly solved by:
Richard Johnson | La Jolla, California |
2. Keith Mealy | Cincinnati, Ohio |
3. Walt Arrison | Philadelphia, Pennsylvania |
4. John Funk | Ventura, California |
5. Hae-Jean Jung | Fort Collins, Colorado |