Associated Topics || Dr. Math Home || Search Dr. Math

### Walking the Shortest Distance

```Date: 10/07/2002 at 20:51:25
From: Lisa Gallagher
Subject: Riddle

Hello,

I was wondering if you could help me with the following problem:

A single boy lives in each of n equally spaced houses on a straight
line. At what point should the boys meet so that the sum of the
distances that they walk from their houses is as small as possible?

Lisa Gallagher
```

```
Date: 10/08/2002 at 16:46:19
From: Doctor Ian
Subject: Re: Riddle

Hi Lisa,

Let's say that there are N boys, and they live at locations 0, 1, 2,
3, 4, and so on, up to (N-1).

Now, suppose they meet at the home of the boy who lives at 0. He won't
have to walk at all. The distances the other boys will walk will be
1, 2, 3, and so on. So the sum of the distances will be

0 + 1 + 2 + 3 + 4 + ... + (N-1)

We can figure out what that is later, if we need to. Now suppose that
they decide instead to meet at the home of the boy who lives at 1.
Now boy[0] will have to walk 1 unit, boy[1] won't have to go anywhere,
boy[2] will have to walk 1 unit, and so on.  So the sum of the
distances will be

1 + 0 + 1 + 2 + 3 + ... + (N-2)

Now, this is interesting, because we took a big value off of the right
end, and put a much smaller value on the left end. We could keep doing
that by shifting the meeting place to the right:

2 + 1 + 0 + 1 + 2 + 3 + ... + (N-3)

3 + 2 + 1 + 0 + 1 + 2 + 3 + ... + (N-4)

and so on. At what point will this be as small as possible?

Of course, there is nothing that says that they have to meet at one of
their homes. But suppose you find a home that gives the minimum value
for all the homes. Could you possibly make the distance smaller by
moving away from that home?

Is this enough to get you started?

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

```
Date: 10/08/2002 at 19:23:21
From: Lisa Gallagher
Subject: Riddle

Hi,

I just want to make sure that I understand. So the boys should meet so
that the sum of the distances that they walk from their houses is as
small as possible because 2 + 1 + 0 + 1 + 2 = 6, which is the smallest
sum if five boys are walking from their houses?

Lisa
```

```
Date: 10/08/2002 at 19:33:33
From: Doctor Ian
Subject: Re: Riddle

Hi Lisa,

Your example looks like you've got the concept down, at least for an
odd number of boys. You might think about what has to change if the
number of boys is even instead of odd.

Thanks for asking the question. It was interesting to think about. If
I had to guess, I'd say that it was probably designed to get you to

For example, what would change if the boys lived at locations 0, 1, 2,
4, 8, 16, and 32? Or at locations 0, 1, 2, 3, 4, 5, 6, and 21?

- Doctor Ian, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Basic Algebra
High School Puzzles
High School Statistics

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