[Statistics] Help me solve this

Ferrus

First of all I'm not really sure if this falls under the No Homework rule since I'm obviously not asking anyone to DO my homework for me. I'm simply not getting what my professor wants me to do here. I'm sorry if this thread violates any rules.

The question is this:
"There are 15 houses in a village along a straight road. The space between the individual houses varies randomly. Where should the post office be placed so the mailman has to walk the least possible distance while delivering the mail and returning to the office after each delivery."

Intuitively, I'd say he wants me to do... something... with the median value. So the post office should be placed such that 50% of the houses are to the left and 50% are to the right -> Median.

However, I'm unsure wether or not this would make for the least possible delivery-distance. :?

So, any thoughts on this?

Sipex

Depends, is, in the middle of the road with 50% of the houses on the left and 50% on the right an option?

edit: I mean, like, the middle of the street, not just wedged between houses but where cars drive.

Ferrus

I see where you're going with that but I think an answer containing "ON the road" would get me negative points if anything.

I'm simply not sure what I should answer here. My professor is somewhat pedantic when it comes to these assignments.

Sipex

Give him a paragraph answer then.

You know 'Assuming that the post office cannot be place in the middle of the road then...'

TheSmacker

1/2 of the houses on each side wouldn't necessarily be the correct answer if they're a random distance apart.

You'd need to find some way to express the distance between each house and the post office as a function, and then minimize the sum of all the functions w.r.t the post office....something along those lines?

Clipse

I agree with TheSmacker about thinking of the problem in terms of minimizing a function, but I'm not positive that the median is wrong.

If we call the house locations h[1], h[2], ... h[15], then we want a post office location p which minimizes the function

Sum( |h - p| ).

Or at least, that is the only interpretation of the problem I can see. I would suggest looking at a smaller number of houses to start with -- maybe 3 -- and see if you can solve it there and get some ideas for a more general solution that would apply in the case of 15 houses.

Ferrus

That function looks good, thanks! I will have to discuss this with my group when I get the chance since I'm generally horrible at math. The others can probably work with that function, though.

TheSmacker

Yeah I agree with Clipse and that it probably will be the median. As usual I got that mixed up with the mean.

samedi

Maybe I am missing something, but if the houses are along a straight road then it seems that barring the ability to place the post office in the middle of the street, that it wouldn't matter because he has to make a complete cycle regardless of where it is...

consider:

X X XX X X X

---

X X X X X

no matter, where you place the Post office, the fastest path will be to go to all the houses in one direction, cross the street, go to all the houses on that side, cross again and return. Distance travelled = (sum of distance on north) + sum of distance on south side+2*width of street.

X X XX X X <-X/\
|

---

|
\/->X X 0-> X X X


The minimization equation posted above would only work if he had to walk back and forth between the post office and each house, which he doesn't have to do. If the houses are placed randomly then its almost like a travelling saleman problem.
http://en.wikipedia.org/wiki/Travelling_salesman_problem

edit: Sorry the diagrams came out all messed up in the post, I was trying to illustrate travelling around the circuit

Ferrus

He DOES have to walk back to the office after every delivery.

It wouldn't be your average "realistic" math assignment otherwise.

Also I assume "along a straight road" means they're only on one side of the road.

Cognisseur

It matters what sort of 'random' distance you have between houses. Random could mean literally as likely to be 5m as 5000km, or we could be talking more stats-like and say it's random within the confines of a normal distribution.

If it's the former, then I agree you should go with the median in order to cover your ass in case of outliers.
If it's the latter, then I'd go with the mean because statistically when you know no other information (except that info is distributed in a normal distribution fashion) then the mean would offer you the closest estimation of average distance to all points in the distribution.

samedi

ahh, ok, sorry. I missed that the first time.

I think there is an easier solution though.

Consider 5 homes, h0,h1,h2,h3,h4

and the distances d0,d1,d2,d3 where d0=dist(h0,h1), d1=dist(h1,h2), d2=dist(h2,h3) and d3=dist(h3,4)

Given that to get from any house hi to house hi+n, the post must travel from hi->hi+1 from h(i+1)->h(i+2)... h(n-1)->hn, we can consider the problem as:

t0*d0+ t1*d1+t2*d2+t3*d3 where ti is the number of time the postman travels the distance di

if we consider the situation where the post office is right next to house 0, we would have to travel distance d0 4 times (once for each house to the right of the post office), giving us:

4*d0+3*d1+2*d2+1*d3

For each position (where the post office is right next to a house) we have:
P=1
1*d0+3*d1+2*d2+1*d3
p=2
1*d0+2*d1+2*d2+1*d3
p=3
1*d0+2*d1+3*d2+1*d3
p=4
1*d0+2*d1+3*d2+4*d3

So clearly we want the post office next to house 2 (the middle house), because regardless of what the values are for the di's that situation minimizes the sum.

In the more general sense we want the post office located next to house at position floor(N/2) where N is the total number of homes, the 7th house in your case. In other words we want the same number of houses to the left as we have to the right, regardless of what the distances are between the houses.

Ferrus

As a side note, the next question in the assignment is "What's the solution to this problem if there are 16 houses?" which strongly suggests that the answer to a) simply means the median formula for odd numbers and the answer to b) means the formula for even numbers.

I sent your solutions to my group to see what they think of this. I have the feeling this shouldn't be THAT complicated, given that we're early in the semester.

Super Kipper

Hmm, well I guess this now is answering your homework... but, if you want a more intuitive answer, think of the case with only two houses - the delivery distance is the same for any position of the office between those two, larger if outside the pair.

If you then think about 4 houses, you can apply this logic to both the outer pair and inner pair: anywhere between the inner pair is the best. This works for any number of pairs (even numbers of houses)

For odd numbers, you can pair off all but one in the middle - then, clearly, the position of that house is the best place for the office.

All assuming that all the houses always get the same number of deliveries...

Clipse

Ferrus wrote: »

As a side note, the next question in the assignment is "What's the solution to this problem if there are 16 houses?" which strongly suggests that the answer to a) simply means the median formula for odd numbers and the answer to b) means the formula for even numbers.

I sent your solutions to my group to see what they think of this. I have the feeling this shouldn't be THAT complicated, given that we're early in the semester.

There's a solution which is less tedious for large numbers of houses than samedi's and more formal than Super Kipper's. I'll give an outline of it and spoiler the details.


First, show that there is always a solution in which the location of the post office is precisely the same as the location of one of the houses (ie, p = h for some i).

Suppose p is not located on a house, and that p has m houses to the left of it and n houses to the right of it. If m >= n, we can move p left to the nearest house and the result will be as efficient or more efficient. Likewise if m <= n, we can move p to the right.

To see this, suppose that the distance between p and the house to its left is d. Then moving p to the house nearest on the left will decrease the total travel necessary by 2md and increase the total travel necessary by 2nd. Since m >= n, 2md >= 2nd, so the route is at least as efficient as the one we begun with. Similarly if m <= n and going right.

Now it suffices only to consider cases in which p is located at one of the houses.

Suppose p is located at a house, and there are m houses to the left of p and m houses to the right. If m > n, moving to the next house to the left (distance d away) will decrease the total distance traveled by 2md and increase the total distance traveled by 2(n+1)d. Since m > n and m and n are both integers, m >= n+1, so 2md >= 2(n+1)d, as we want. If n > m we have the opposite case and can move to the next house to the right. If n = m, moving in either direction will have a net increase in total length traveled.

That completely handles the case in which there are an odd number of houses. n = m implies p is located at the median, and we can see that moving towards the median will never make the route less efficient, and moving away from the median makes the route less efficient. Thus, the median is necessarily a solution.

For an even number of houses there's a bit of extra that I'll leave to you -- show that the two houses closest to the middle are both solutions, and that any point between the two is a solution as well. Then the median of the list is a solution, as it lies between the two middlemost houses.