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? 

Thanks for your help.
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?

Thanks for all your help.
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 
think about averages.  

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/