November 2, 1998
Problem of the Month

A Walk in Winchester

A map of downtown Winchester is shown below. Billy lives at the corner of Monmouth and Stewart.

Betty lives at the corner of Cameron and Boscawen.

Billy decides that he will visit Betty every day after school until he has tried every different route from his house to her house.

Billy travels only east and north.

How many different routes can Billy take to Betty's house?

 
			 
            N
            ^  
            |     
       W <--+--> E  
            |
            ! 
            S
			
Boscawen   +---+---+---+---O---+
           |   |   |   |   |   |
Cork       +---+---+---+---+---+             
           |   |   |   |   |   |     
Clifford   +---+---+---+---+---+         
           |   |   |   |   |   |      
Cecil      +---+---+---+---+---+   
           |   |   |   |   |   |   
Leicester  +---+---+---+---+---+   
           |   |   |   |   |   |
Monmouth   O---+---+---+---+---+
           |   |   |   |   |   |
          
           S   W   B   L   C   K
           t   a   r   o   a   e
           e   s   a   u   m   n
           w   h   d   d   e   t
           a   i   d   o   r
           r   n   o   u   o
           t   g   c   n   n
               t   k
               o
               n

             

Solution to the Problem:

The answer is 126 different ways.

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 east.

            N
            ^  
            |     
       W <--+--> E  
            |
            ! 
            S 

Boscawen   1---6--21--56--126--+
           |   |   |   |   |   |
Cork       1---5--15--35--70---+             
           |   |   |   |   |   |              
Clifford   1---4--10--20--35---+                
           |   |   |   |   |   |      
Cecil      1---3---6--10--15---+           
           |   |   |   |   |   |     
Leicester  1---2---3---4---5---+    
           |   |   |   |   |   |
Monmouth   1---1---1---1---1---+
           |   |   |   |   |   |
          
           S   W   B   L   C   K
           t   a   r   o   a   e
           e   s   a   u   m   n
           w   h   d   d   e   t
           a   i   d   o   r
           r   n   o   u   o
           t   g   c   n   n
               t   k
               o
               n

             

Alternate solution
C. W. Larson from Northern Arizona University wrote that Billy can only take one route to Betty's house since by traveling only north and east, once he gets to Betty's house, he can never return to his own!

Correctly solved by:

1. Christophe W. Larson	Flagstaff, AZ (Northern Arizona University)
2. Trey Genda	Winchester, VA

Send any comments or questions to: David Pleacher