Answer to September 17, 2001 Problem

The Fort Collins Problem 

 
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