Answer to November 2, 1998 Problem

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?


Boscawen   +---+---+---+---O---+
           |   |   |   |   |   |
Cork       +---+---+---+---+---+            N
           |   |   |   |   |   |            ^  
Clifford   +---+---+---+---+---+            |     
           |   |   |   |   |   |       W <--+--> E  
Cecil      +---+---+---+---+---+            |
           |   |   |   |   |   |            ! 
Leicester  +---+---+---+---+---+            S 
           |   |   |   |   |   |
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:
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.

Boscawen   1---6--21--56--126--+
           |   |   |   |   |   |
Cork       1---5--15--35--70---+            N
           |   |   |   |   |   |            ^  
Clifford   1---4--10--20--35---+            |     
           |   |   |   |   |   |       W <--+--> E  
Cecil      1---3---6--10--15---+            |
           |   |   |   |   |   |            ! 
Leicester  1---2---3---4---5---+            S 
           |   |   |   |   |   |
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 travelling 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