At the end of each growing season, Joy likes to prune dead leaves from her favourite tree. She does this by cutting branches. For this tree, shown below, there are \(15\) leaves she wants to remove. She decides to give an approximate time it will take to cut each branch. These times are shown for each branch.
When a branch is cut, all branches and leaves attached to it are removed from the tree. For example, if you cut the branch labelled with \(15\), the three leftmost leaves will be removed.
What is the shortest amount of time in which Joy can remove all \(15\) leaves?
We label the leaves \(A\) through \(O\) in the diagram.
Notice that the three leftmost leaves (\(A, B,\) and \(C\)) do not share any branches with the rest of the leaves (\(D\) through \(O\)). Therefore, removing these leaves will have no impact on removing the rest. The same is true for the eight centre leaves (\(D\) through \(K\)) and the four rightmost leaves (\(L, M, N,\) and \(O\)). This means that the shortest amount of time needed to remove all \(15\) leaves is the sum of the shortest amount of time needed to remove the leftmost leaves, the centre leaves, and the rightmost leaves.
To remove the leftmost leaves we have two options: remove them all at once (which takes \(15\) minutes), or remove them individually (which takes \(5+5+6 = 16\) minutes). The shortest amount of time needed to remove the leftmost leaves is thus \(15\) minutes.
To remove the rightmost leaves we have three options: remove them all at once (which takes \(9\) minutes), remove them individually (which takes \(1 + 3 + 1 + 3 = 8\) minutes), or remove \(N\) and \(O\) together and \(L\) and \(M\) individually (which takes \(5+1+3 = 9\) minutes). The shortest amount of time needed to remove the rightmost leaves is thus \(8\) minutes.
To remove the centre leaves we notice that if we remove them all at once it will take \(25\) minutes, and if remove them in two groups (leaves \(D\), \(E\), \(F\), \(G\) on the left centre branch and then leaves \(H\), \(I\), \(J\), \(K\) on the right centre branch) the time to do so is \(10 + 11 = 21\) minutes. Since \(21\) minutes is less than \(25\) minutes, to find the least amount of time we can look at first minimizing the time to remove the leaves on the left centre branch and then minimizing the time to remove the leaves on the right centre branch.
To remove the leaves on the left centre branch we have five options: remove all the leaves together (which takes \(10\) minutes); remove them individually (which takes \(2 +3 + 2 + 5 = 12\) minutes); remove \(D\) and \(E\) together and \(F\) and \(G\) together (which takes \(6 + 6 = 12\) minutes); remove \(D\) and \(E\) together and \(F\) and \(G\) individually (which takes \(6 + 2 + 5 = 13\) minutes); or remove \(D\) and \(E\) individually and \(F\) and \(G\) together (which takes \(2 + 3 +6= 11\) minutes). This means the least amount of time to remove the leaves on the left centre branch is \(10\) minutes.
To remove the leaves on the right centre branch we have four options: remove all the leaves together (which takes \(11\) minutes); remove them individually (which takes \(2 +4 + 3 + 2 = 11\) minutes); remove \(H\) individually and remove \(I, J\), and \(K\) together (which takes \(2+8 = 10\) minutes); or remove \(H\) and \(I\) individually and remove \(J\) and \(K\) together (which takes \(2 + 4 +6= 12\) minutes). This means the least amount of time to remove the leaves on the right centre branch is \(10\) minutes. This further means the least amount of time to remove the centre leaves is \(10 + 10 = 20\) minutes.
Therefore, the least amount of time to remove all \(15\) leaves is \(15 + 8 + 20 = 43\) minutes. Joy can achieve this time when she cuts the branches that are shown below as dashed.
