Fewest Number of Stops

Date: 09/12/2001 at 11:42:48
From: John
Subject: Algebra

At some stops, the SLU Express bus picks up 5 people. At other stops, 
it picks up 2 and, at the same time, lets off 5. There are no other 
stops but these. 

It starts its run empty and picks up 5 people, and at the end it has 
11 people aboard. If the number of stops is greater than 17, what is 
the fewest number of stops the bus makes?

Date: 09/12/2001 at 14:34:56
From: Doctor Ian
Subject: Re: Algebra

Hi John,

Basically, there are two things that can happen at a stop. The number 
of passengers can go down by 3, or it can go up by 5. So we can make a 
diagram in which each of these paths is represented as

     N-3
    /
   N
    \
     N+5

Starting with 5 passengers, it looks like this:

                          back to 5
                         /
             1     3    /
            /  \ /   \ /
     2     4    6     8 
    /  \  /  \ /  \  /   \
  5      7    9    11     13
    \  /  \  /  \  / \   /
     10    12    14    16
       \  /  \  /  \  /  \
        15    17    19    21
          \  /  \  /  \  /
           20    22    24


Note that there are lots of 6-step paths from 5 to 11, e.g., 

  5 -> 2 -> 7 -> 12 -> 9 -> 14 -> 11

  5 -> 10 -> 15 -> 12 -> 17 -> 14 -> 11

Note that we can also loop around, to increase the number of stops:

 [5 -> 2 -> 7 -> 4 -> 9 -> 6 -> 3 -> 8 ->] 5 -> 2 -> 7 -> 12 -> 9 -> 14 -> 11
 \_______________________________________/
     Repeat as often as desired

So the problem now becomes one of finding a loop of the right size (k) 
such that 

  nk + 6 > 17

Can you take it from here? 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/