First off, I had been working on this puzzle–trying to derive an equation or two out of it–over the past two years. I was first presented with the puzzle at a science museum I used to work part-time at. Intrigued by how mathematically intuitive it is–at least, that’s how I immediately perceived it–I ruminated about possible mathematical patterns behind it ever since.
Without making this post too wordy, let’s dive into the simplified version of this “free-and-easy” paper I wrote earlier this year.
This paper is the author’s personal side project and is of no affiliation to any institution or courses. The paper is a rookie attempt to deriving mathematical expressions of the well-known puzzle, the bridge and torch problem. The problem is about finding the shortest time needed for n people to cross a bridge at night. The catch is the bridge can only support at most two persons at a time, and the two persons will cross the bridge at the speed of the slower one. Moreover, a torch is needed for each and every crossing, and the torch has a finite time of burning. Thus, the puzzle is a problem to determine the possible shortest time from the choice of the two persons per crossing against the finite burning time of the torch. The result of this paper gives into fruition of a set of three equations—vector forms describing the game mechanics of the logic solution, even-valued n function and odd-valued n function.
The bridge and torch problem is a well-known puzzle. A logic puzzle that deals with commonly four people, a bridge and a torch. Four people have to cross the bridge at night. The bridge can only support at most two people at a time. There is only one torch available that must be used at every crossing—that must be walked back and forth. Different people walk at a different speed. Since the bridge can only hold two persons at a time, the pair has to cross the bridge at the rate of the slower person’s pace. The main problem of the puzzle is that the torch has a finite burning time. Therefore, the shortest time needed to get all four people crossing the bridge before the torch burns out is to be solved and determined.
The Existing Logic Solution
The solutions for the bridge and torch problem are abundant in the Internet. Nonetheless, all of the resources bear almost the same method or solution. The broadly-accepted solution is of basic intuitive logic with the conventional setup—a total of four people, n = 4, and is presented as follows:
- The solution starts with letting the two fastest persons to cross the bridge first. This is to ensure the availability of the fastest person on both sides of the bridge.
- Amongst the two fastest, the faster person crosses the bridge back to the group with the torch. This is to minimise time taken possible at the outset.
- The crucial part—the second pair crossing the bridge is being the two slowest. This is a clever trick so as to let the second slowest person to follow the pace of the slowest crossing the bridge once and for all, and thus the final time taken is devoid of that of the time taken by the second slowest.
- Consequently, the second fastest being the only fastest person at the destination-end of the bridge, so the second fastest crosses the bridge back with the torch.
- Finally, the solution of the puzzle ends with the two fastest being at the start-end of the bridge again, thus they cross the bridge with the pace of the second fastest and the all four people has safely crossed the bridge before the torch burns out, and therefore the puzzle is solved.
The Underlying Sequence
This paper is to derive the mathematical expressions of the existing logic solution with arbitrary n-persons involved in the dilemma. We further assume that the different time taken for different person in the dilemma to be consecutively as such, 1, 2, 3, 4, … , n unit of time. Where n is the time taken of the slowest person as well as representing the total number of persons in the problem. Subsequently, we denote the abovementioned time taken for each person to cross the bridge as such, n_1 = 1, n_2 = 2, n_3 = 3, n_4 = 4, … and so on.
Next, we illustrate the existing logic solution to visualize the bridge and torch problem. Figure 1 shows the illustration of the existing logic solution up to n = 9.
In reference to Figure 1, for each n, the left column is the start-end of the bridge and the right column is the destination-end of the bridge. The chronology of the problem is read from top to bottom of the table for each n. The right-pointed arrow indicates the action of crossing the bridge toward the destination-end with the accompanying number seen in the same row denotes the time taken by the slower person of the pair crossing the bridge. Likewise, the left-pointed arrow indicates of crossing back to the start-end. T(n) is the function of the total time taken of the solution with n persons. It is shown that the solution for n = 2, 3, 4, 5, 6, 7, 8 and 9 is T(n) = 2, 6, 11, 16, 22, 28, 35 and 42, respectively. The most crucial part of the visualization is the recurrence of a smaller T(n) after every four moves of the solution of the problem for any given n. This is the consequential bit of the nature of the logic solution in the following derivations of its mathematical expressions.
Skipping some mathematical workings that you can find in the actual paper, presented below is the general vector form of the game mechanics of the logic solution to the bridge and torch problem,
Equation (2) is a complete general form of Equation (1) with determined third and fourth terms. However, this has made Equation (2) restricted to domains such that n is equal to or greater than 4. Also, this has called forth for the ad hoc assumptions of T(2) = 2, T(3) = 3 + 3, T(1) = 0 and T(0) = 0. All of which, we will look into it in the following derivations.
In regards to the derivation of the mathematical expressions describing the logic solution of the bridge and torch problem for any given arbitrary n-persons of the dilemma, we may separately derive an equation for even-valued n and for odd-valued n. This is for the reason of the existence of the constant, 2 and the term, [3+3] in the even-valued n and in the odd-valued n, respectively. It is also certainly for the reason that the parity of n does have its own unique progression or series—as we have seen in the previous part and that, we will look into it in the following steps.
Even-valued n Problem
As usual, mathematical derivations can be very nasty to laypersons–that which one can refer to all of it in the actual paper. Going straight to the result that we derived for the even-valued n problem, presented below is the mathematical expression of the logic solution to the bridge and torch problem for even-valued n-persons in the dilemma,
Odd-valued n Problem
Likewise, for interested readers, all the derivations can be perused in the actual paper. Below is the mathematical expression of the logic solution to the bridge and torch problem for odd-valued n-persons in the dilemma,
Going back to the square one, the bridge and torch problem is a classical puzzle by which the shortest time possible of n-people to safely crossing the bridge is to be solved. There are three major dilemmas in the bridge and torch problem. Firstly, the setting is at night-time and thus the torch is needed for crossing the bridge to and fro but it has a finite burning period that which just a tad bit greater than the supposed possible shortest time taken of the solution. Secondly, the bridge can only safely support two persons at a time. The last dilemma, for any given n-persons, every person crosses the bridge at a different level of speed and the pair crosses the bridge at a time follows the pace of the slower one. Commonly, the problem presents the people’s crossing speed in a consecutive counting manner with the starting unit usually of 1. For convenience, the paper applies the same assumptions when tackling the problem. In the result, the paper has made into fruition of three major derivations from the existing logic solution. Equation (1) and Equation (2) are of the same general form and describe the general game mechanics of the existing logic solution through vectors. Equation (3) expresses the final total time taken by even-valued n-persons. Equation (4) expresses the final total time taken by odd-valued n-persons. All mathematical expressions derived in the paper is expressed in T(n) as a function n. Where, T(n) is the final total time taken by n-persons crossing the bridge under said dilemmas, and n is any given arbitrary number of persons in the problem.