Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/