Solution

In Gridville, the POTW Delivery Company needs to deliver nine packages to nine different locations. In the diagram below, the location where they start is labelled with an \(S\). The nine other circles indicate where the nine delivery locations are. These locations are joined by roads, which are shown as lines. The number beside each line indicates the average time, in minutes, it will take to travel along that road.

10 circles are arranged into 2 rows of 5.

The top-left circle is marked \(S\).

Each circle in the top row is connected by a line to the next circle in the top row. The four connecting lines, from left to right, have numbers \(3\), \(3\), \(4\), and \(6\).

Each circle in the top row is also connected by a line to the circle directly below it in the bottom row. The five connecting lines, from left to right, have numbers \(2\), \(5\), \(1\), \(8\), and \(4\).

Each circle in the bottom row is connected by a line to the next circle in the bottom row. The four connecting lines, from left to right, have numbers \(1\), \(3\), \(2\), and \(5\).

If the POTW Delivery Company does not want to visit any location more than once, but can finish at any location, what is the shortest amount of time that they will take to deliver the nine packages?

Solution

There are only five possible paths that start at \(S\) and visit each of the locations exactly once:

Each path is a different sequence of connected lines from the original diagram. Following the lines in each path means moving through the two rows of circles as described below.

Path 1) goes to the right four times, along the four lines in the top row, to the fifth circle in the top row, then down to the fifth circle in the bottom row, then to the left four times, along the four lines in the bottom row, ending at the first circle in the bottom row. The lines forming this path, in order, have the numbers \(3,3,4,6,4,5,2,3,1\).

Path 2 goes down to the bottom row, then right four times along the bottom row, then up to the top row, then left three times along the top row, ending at the second circle in the top row. The lines forming this path, in order, have the numbers \(2,1,3,2,5,4,6,4,3\).

Path 3) goes down to the bottom row, then right, then up, then right three times along the top row, then down, then to the left twice along the bottom row, ending at the middle circle in the bottom row. The lines forming this path, in order, have the numbers \(2,1,5,3,4,6,4,5,2\).

Path 4) goes down, right, up, right, down, right twice, up, then left, ending at the fourth circle in the top row. The lines forming this path, in order, have the numbers \(2,1,5,3,1,2,5,4,6\).

Path 5) goes down, right, up, right, down, right, up, right, then down, ending at the fifth circle in the bottom row. The lines forming this path, in order, have the numbers \(2,1,5,3,1,2,8,6,4\).

To justify this, notice that we have two choices for where to travel from \(S\): down or right.

Therefore, the shortest amount of time to deliver the nine packages is \(29\) minutes.

Problem of the Week
Problem E and Solution
Special Delivery

Problem

Solution

Problem of the Week Problem E and Solution Special Delivery

Problem

Solution

Problem of the Week
Problem E and Solution
Special Delivery