Walking the Shortest DistanceDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/