September 17, 2001
Problem of the Month

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 to the Problem:

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 zeros 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

Send any comments or questions to: David Pleacher