Midville Truck Puzzle

[Guest]

The attached image shows the layout of streets in the centre of a small town, Midville, in which every line segment (e.g from A to B) is exactly 1 kilometer.

The City Council has just resurfaced all of the streets and now the line down the middle of each street must be repainted. The truck used for this purpose is very inefficient as far as petrol consumption is concerned, and so the Council would like to have the truck travel the shortest distance possible.

The truck is currently at the point A but after the job it must be parked at point B. What is the minimum distance that the truck can travel to complete this task? What route should be followed to achieve this minimum?

I would really love an explanation to this problem!

[Guest]

The smallest I can get is 14. Here is the path: A-G-F-E-G-D-C-G-B-A-F-E-D-C-B. I would be interested to see if there is anything shorter.

[witzar]

The truck needs to visit point C at least 2 times to paint all 3 adjacent streets.

So it will arrive at point C at least twice and will leave it at least twice,

so at least once it will drive on already painted road.

The same applies to points D, E, F.

Since each of the four points above requires an extra segment of truck's road,

at least two extra segments are required (one extra segment per two points).

City roads have 12 segments total, so there could no road shorter than 12+2=14.

[Guest]

In any situation with nodes connected by equal length lines, you can determine the minimum distance to travel all the paths simply by counting the number of odd nodes (odd number of lines connected to the node) and number of total segments. If there are 2 or fewer odd nodes, then as long as you start at one of the odd nodes, you can travel the entire path without retracing any of the lines and the answer is just the number of segments. If there are more than 2 odd nodes, that will require at least one line being retraced, with at least 1 retraced line for every pair of additional odd nodes above the first 2. In this case, we have 6 odd nodes and 1 even node. So we count the segments (12) and add 1 for each pair of the extra odd nodes (6-2=4; 4/2=2) and we get 14.

I'm pretty sure this will always work. I tried drawing a bunch and it worked, but I don't have a proof. Hope this makes sense.

[Guest]

How might it change the problem if we added a differing cost for taking a 120 degree turn versus a 60 degree turn? Suppose the truck had a wide turning radius and would require a greater effort and thus higher emissions for taking the sharper turn. Alternatively, we could limit the truck to only being able to go straight or take a 60 degree turn at an intersection. How might the solution be changed?

Does the minimum of 14 segments still hold true?

Edited September 1, 2010 by Egghead

[Guest]

k = the petrol consumption for 1 kilometer;

c = the petrol consumption for a wide turn;

v = the petrol consumption for a sharp turn:

P_c = the petrol consumption for a wide turn to park truck for next use;

P_v = the petrol consumption for a sharp turn to park truck for next use;

If one needs to include parking (the re-orienting of the truck for next use),

then there is effectively no difference in the shortest routes.

If we exclude parking, given c < v, 14k + 5c + 5v would be more economical.

A-F-E-D-C-B-E-F-C-D-A-B => 14k + 4c + 6v + 1P_c

A-F-E-D-C-B-A-D-C-F-E-B => 14k + 5c + 5v + 1P_v

The task would be impossible if only wide turns were permitted. If it was required

that all turns be sharp turns, then one possible solution is:

A-F-C-D-G-E-D-G-E-F-G-A-B-G-C-B = 16k + 14v + 1P_v

[witzar]

In any situation with nodes connected by equal length lines, you can determine the minimum distance to travel all the paths simply by counting the number of odd nodes (odd number of lines connected to the node) and number of total segments.

...

I'm pretty sure this will always work.

Think for example about a graph in a shape of a cross (or letter X): four arms, each arm made of 100 segments. This graph has 400 edges (segments) and only 4 odd nodes (one at the end of each arm). You can start and finish where You want. Can you traverse it in 402 steps? Can You do better then 600?

PS If You don't like "dead ends" (vertices with only one segment)in graph, You can add a triangle (loop made of 3 segments) at the end of each arm.

[Guest]

I managed to get thirteen, but do it yourself, this is an assignment question =.= [PBL]

[Guest]

There is no solution with length 13 or less. There are 1008 solutions with length 14 and 10296 solutions of length 15.

[Guest]

A-B-C-G-F-A-G-D-C-D-E-G-F-E!!!!!!!!!!!!!!!!!!!!!!!

ANOTHER SOLUTION !!!!!! YEAH

The attached image shows the layout of streets in the centre of a small town, Midville, in which every line segment (e.g from A to B) is exactly 1 kilometer.

The City Council has just resurfaced all of the streets and now the line down the middle of each street must be repainted. The truck used for this purpose is very inefficient as far as petrol consumption is concerned, and so the Council would like to have the truck travel the shortest distance possible.

The truck is currently at the point A but after the job it must be parked at point B. What is the minimum distance that the truck can travel to complete this task? What route should be followed to achieve this minimum?

I would really love an explanation to this problem!

[Guest]

A-B-C-G-F-A-G-D-C-D-E-G-F-E!!!!!!!!!!!!!!!!!!!!!!!

ANOTHER SOLUTION !!!!!! YEAH

What about from point B to point G?

[Guest]

stavros is right, the answer is 13...

As for the route:

A -> F = 1, F -> C = 2, C -> B = 1, B -> E = 2, E -> D = 1, D -> C = 1, C -> F = 2, F -> E = 1, E -> B = 2

If you add all the numbers up, you will get 13. Unfortunately, I don't have the time to come up with a mathematical proof for you, if there is one. Keep in mind, you try to solve this with calculations alone, you will probably get 14 most of the time. Try out the route for yourself if you are not satisfied.

[Guest]

stavros is right, the answer is 13...

As for the route:

A -> F = 1, F -> C = 2, C -> B = 1, B -> E = 2, E -> D = 1, D -> C = 1, C -> F = 2, F -> E = 1, E -> B = 2

If you add all the numbers up, you will get 13. Unfortunately, I don't have the time to come up with a mathematical proof for you, if there is one. Keep in mind, you try to solve this with calculations alone, you will probably get 14 most of the time. Try out the route for yourself if you are not satisfied.

thanks dmjohnsonn. Unfortunate my root must be the oposite so intead of finishing to E i finish to B.

[Guest]

thanks dmjohnsonn. Unfortunate my root must be the oposite so intead of finishing to E i finish to B.

Neither yours, stratos, nor dmjohnsonn's route is correct as the route of 13km leaves one or more of streets unpainted. Recheck your route.

[Guest]

Neither yours, stratos, nor dmjohnsonn's route is correct as the route of 13km leaves one or more of streets unpainted. Recheck your route.

yes, in their answer 3 walls are unpainted. My answer is 14:)

A-G-C-B-A-F-G-D-C-D-E-F-E-G-B=14