A tour company is planning adventure day trips to a small island. Every morning, a boat will take a group of people to the dock on the west side of the island. People can take different routes across the island, doing different activities along the way. Due to equipment and/or time constraints, there is a maximum number of people that can do each activity per day. The final activities will finish at the dock on the east side of the island, where a boat will take everyone back to the mainland in the evening.
A map of the island is given below. Nine different locations on the island are marked with the letters \(A\) through \(H\) and \(J\), where \(A\) marks the dock on the west side and \(J\) marks the dock on the east side. Arrows, each labelled with a travel activity and a maximum number of people, indicate how people can move between locations on their way from \(A\) to \(J\).
What is the maximum number of people that can travel from \(A\) to \(J\) in one day using only the routes and activities shown?
This problem was inspired by a past Beaver Computing Challenge (BCC) problem.
The maximum number of people that can travel from \(A\) to \(J\) in one day using only the routes and activities shown is \(20\). First we will show a possible way that \(20\) people can travel from \(A\) to \(J\), and then we will prove that this is the maximum.
After the \(20\) people arrive at \(A\), \(5\) of them should go to \(B\), \(10\) of them should go to \(C\), and \(5\) of them should go to \(D\). The people will then be distributed as follows.
| Location | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) | \(G\) | \(H\) | \(J\) |
|---|---|---|---|---|---|---|---|---|---|
| Number of People | 0 | 5 | 10 | 5 | 0 | 0 | 0 | 0 | 0 |
From \(B\), the only possible route goes to \(E\), so everyone from \(B\) should go to \(E\). From \(C\), \(5\) of the people should go to \(E\) and the remaining \(5\) people should go to \(D\). The people will then be distributed as follows.
| Location | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) | \(G\) | \(H\) | \(J\) |
|---|---|---|---|---|---|---|---|---|---|
| Number of People | 0 | 0 | 0 | 10 | 10 | 0 | 0 | 0 | 0 |
From \(D\), the only possible route goes to \(F\). Similarly from \(E\), the only possible route goes to \(G\). So all of the people at \(D\) should go to \(F\) and all of the people at \(E\) should go to \(G\). The people will then be distributed as follows.
| Location | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) | \(G\) | \(H\) | \(J\) |
|---|---|---|---|---|---|---|---|---|---|
| Number of People | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 0 | 0 |
From \(F\), \(5\) of the people should go to \(G\) and the remaining \(5\) people should go to \(H\). The people will then be distributed as follows.
| Location | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) | \(G\) | \(H\) | \(J\) |
|---|---|---|---|---|---|---|---|---|---|
| Number of People | 0 | 0 | 0 | 0 | 0 | 0 | 15 | 5 | 0 |
Everyone from \(G\) and \(H\) should then go to \(J\). Using these routes, a total of \(20\) people can travel from \(A\) to \(J\). Note that this is not the only possible way for \(20\) people to travel from \(A\) to \(J\).
We now must show that it is not possible for more than \(20\) people to travel from \(A\) to \(J\) in one day. Suppose we separate the island into two groups. The west group contains \(A\), \(B\), \(C\), \(D\), and \(E\). The east group contains \(F\), \(G\), \(H\), and \(J\). In order to travel from \(A\) to \(J\), people must travel from the west group to the east group. However there are only two ways to travel between the west group and the east group. At most \(10\) people can travel from \(E\) to \(G\), and at most \(10\) people can travel from \(D\) to \(F\) in one day. So, in total, at most \(10+10=20\) people can travel from the west group to the east group in one day. Since we have found a way for \(20\) people to travel from \(A\) to \(J\) in one day, it follows that the maximum number of people that can travel from \(A\) to \(J\) in one day is \(20\).