BrainDen.com - Brain Teasers
• 0

# Midville Truck Puzzle

## Question

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!

## Recommended Posts

• 0

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.

##### Share on other sites

• 0

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,

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.

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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?

##### Share on other sites

• 0

k = the petrol consumption for 1 kilometer;

c = the petrol consumption for a wide turn;

v = the petrol consumption for a sharp turn:

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

Pv = 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 + 1Pc

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

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 + 1Pv

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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

##### Share on other sites

• 0

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

##### Share on other sites

• 0

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!

##### Share on other sites

• 0

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?

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.