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
Math Forum Home || Math Library || Quick Reference || Math Forum Search