Five tents, each of a different colour, are to be placed on five different campsites. The five campsites are arranged as shown, with each pair of campsites connected by a path. The number on each path indicates the number of minutes it takes to walk along that path.
Jared wants to start at the blue tent, and take a walk along some of the paths passing the tents in the order green, white, yellow, red, and yellow, before returning to the blue tent.
If Jared wants the total time that he spends walking to be as small as possible, what colour tent(s) should be put in campsite \(C\)?
Not printing this page? You can use our interactive worksheet.
This problem was inspired by a past Beaver Computing Challenge (BCC) problem.
The given sequence of tent colours is blue, green, white, yellow, red, yellow, and blue. This tells us that Jared will pass by all five tents and walk along the following six paths: blue \(\rightarrow\) green, green \(\rightarrow\) white, white \(\rightarrow\) yellow, yellow \(\rightarrow\) red, red \(\rightarrow\) yellow, and yellow \(\rightarrow\) blue. In this sequence, Jared will walk to and from each campsite at least once. Therefore, he needs to walk to and from campsite \(C\) at least once. So the minimum possible time occurs when Jared takes two of the \(3\) min paths that connect to campsite \(C\), and four of the \(2\) min paths. Such a walk would take Jared \(2(3) + 4(2) = 14\) min.
Three such routes are shown, where the tent in campsite \(C\) is blue, white, and red, respectively.
Now we will show why it is not possible for the tent in campsite \(C\) to be yellow or green if Jared’s walk takes \(14\) min in total.
If the tent in campsite \(C\) is yellow, then Jared will have to walk on four \(3\) min paths because he passes the yellow tent twice on his walk. Then the minimum possible time would be \(4(3)+2(2)=16\) min. This is more than \(14\) min. Thus, if the tent in campsite \(C\) is yellow, then Jared’s walk can’t take the minimum time of \(14\) min.
If the tent in campsite \(C\) is green, then in order to achieve the minimum time of \(14\) min, the paths white \(\rightarrow\) yellow, yellow \(\rightarrow\) red, and yellow \(\rightarrow\) blue must each take \(2\) min. However this is not possible because each of the remaining campsites has \(2\) min paths connecting to only two other campsites. So the yellow tent cannot have a \(2\) min path connecting to each of the white, red, and blue tents. This means that one of these paths must take \(7\) min, which would mean the minimum possible time would be \(2(3) + 3(2) + 7 = 19\) min. This is more than \(14\) min. Thus, if the tent in campsite \(C\) is green, then Jared’s walk can’t take the minimum time of \(14\) min.
Therefore, the tent in campsite \(C\) should be blue, white, or red.