The bridge and torch problem (also known as The Midnight Train [1] and Dangerous crossing [2] ) is a logic puzzle that deals with four people, a bridge and a torch. It is in the category of river crossing puzzles, where a number of objects must move across a river, with some constraints. [3]
Four people come to a river in the night. There is a narrow bridge, but it can only hold two people at a time. They have one torch and, because it's night, the torch has to be used when crossing the bridge. Person A can cross the bridge in 1 minute, B in 2 minutes, C in 5 minutes, and D in 8 minutes. When two people cross the bridge together, they must move at the slower person's pace. The question is, can they all get across the bridge if the torch lasts only 15 minutes? [2]
An obvious first idea is that the cost of returning the torch to the people waiting to cross is an unavoidable expense which should be minimized. This strategy makes A the torch bearer, shuttling each person across the bridge: [4]
| Elapsed Time | Starting Side | Action | Ending Side |
|---|---|---|---|
| 0 minutes | A B C D | ||
| 2 minutes | C D | A and B cross forward, taking 2 minutes | A B |
| 3 minutes | A C D | A returns, taking 1 minute | B |
| 8 minutes | D | A and C cross forward, taking 5 minutes | A B C |
| 9 minutes | A D | A returns, taking 1 minute | B C |
| 17 minutes | A and D cross forward, taking 8 minutes | A B C D |
This strategy does not permit a crossing in 15 minutes. To find the correct solution, one must realize that forcing the two slowest people to cross individually wastes time which can be saved if they both cross together: [4]
| Elapsed Time | Starting Side | Action | Ending Side |
|---|---|---|---|
| 0 minutes | A B C D | ||
| 2 minutes | C D | A and B cross forward, taking 2 minutes | A B |
| 3 minutes | A C D | A returns, taking 1 minute | B |
| 11 minutes | A | C and D cross forward, taking 8 minutes | B C D |
| 13 minutes | A B | B returns, taking 2 minutes | C D |
| 15 minutes | A and B cross forward, taking 2 minutes | A B C D |
A second equivalent solution swaps the return trips. Basically, the two fastest people cross together on the 1st and 5th trips, the two slowest people cross together on the 3rd trip, and EITHER of the fastest people returns on the 2nd trip, and the other fastest person returns on the 4th trip.
Thus the minimum time for four people is given by the following mathematical equations: When ,
 |
Assume that a solution minimizes the total number of crossings. This gives a total of five crossings - three pair crossings and two solo-crossings. Also, assume we always choose the fastest for the solo-cross. First, we show that if the two slowest persons (C and D) cross separately, they accumulate a total crossing time of 15. This is done by taking persons A, C, & D: C+A+D+A = 5+1+8+1=15. (Here we use A because we know that using A to cross both C and D separately is the most efficient.) But, the time has elapsed and person A and B are still on the starting side of the bridge and must cross. So it is not possible for the two slowest (C & D) to cross separately. Second, we show that in order for C and D to cross together that they need to cross on the second pair-cross: i.e. not C or D, so A and B, must cross together first. Remember our assumption at the beginning states that we should minimize crossings and so we have five crossings - 3 pair-crossings and 2 single crossings. Assume that C and D cross first. But then C or D must cross back to bring the torch to the other side, and so whoever solo-crossed must cross again. Hence, they will cross separately. Also, it is impossible for them to cross together last, since this implies that one of them must have crossed previously, otherwise there would be three persons total on the start side. So, since there are only three choices for the pair-crossings and C and D cannot cross first or last, they must cross together on the second, or middle, pair-crossing. Putting all this together, A and B must cross first, since we know C and D cannot and we are minimizing crossings. Then, A must cross next, since we assume we should choose the fastest to make the solo-cross. Then we are at the second, or middle, pair-crossing so C and D must go. Then we choose to send the fastest back, which is B. A and B are now on the start side and must cross for the last pair-crossing. This gives us, B+A+D+B+B = 2+1+8+2+2 = 15.
Several variations exist, with cosmetic variations such as differently named people, or variation in the crossing times or time limit. [5] The torch itself may expire in a short time and so serve as the time limit.[ further explanation needed ] In a variation called The Midnight Train, for example, person D needs 10 minutes instead of 8 to cross the bridge, and persons A, B, C and D, now called the four Gabrianni brothers, have 17 minutes to catch the midnight train. [1]
The puzzle is known to have appeared as early as 1981, in the book Super Strategies For Puzzles and Games. In this version of the puzzle, A, B, C and D take 5, 10, 20, and 25 minutes, respectively, to cross, and the time limit is 60 minutes. [6] [7] In all these variations, the structure and solution of the puzzle remain the same.
In the case where there are an arbitrary number of people with arbitrary crossing times, and the capacity of the bridge remains equal to two people, the problem has been completely analyzed by graph-theoretic methods. [4]
Martin Erwig from Oregon State University has used a variation of the problem to argue for the usability of the Haskell programming language over Prolog for solving search problems. [8]
The puzzle is also mentioned in Daniel Dennett's book From Bacteria to Bach and Back as his favorite example of a solution that is counter-intuitive.
The Tower of Hanoi is a mathematical game or puzzle consisting of three rods and a number of disks of various diameters, which can slide onto any rod. The puzzle begins with the disks stacked on one rod in order of decreasing size, the smallest at the top, thus approximating a conical shape. The objective of the puzzle is to move the entire stack to one of the other rods, obeying the following rules:
The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved.
Dynamic programming is both a mathematical optimization method and an algorithmic paradigm. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
The calculus of variations is a field of mathematical analysis that uses variations, which are small changes in functions and functionals, to find maxima and minima of functionals: mappings from a set of functions to the real numbers. Functionals are often expressed as definite integrals involving functions and their derivatives. Functions that maximize or minimize functionals may be found using the Euler–Lagrange equation of the calculus of variations.
Four fours is a mathematical puzzle, the goal of which is to find the simplest mathematical expression for every whole number from 0 to some maximum, using only common mathematical symbols and the digit four. No other digit is allowed. Most versions of the puzzle require that each expression have exactly four fours, but some variations require that each expression have some minimum number of fours. The puzzle requires skill and mathematical reasoning.
This glossary of chess problems explains commonly used terms in chess problems, in alphabetical order. For a list of unorthodox pieces used in chess problems, see Fairy chess piece; for a list of terms used in chess is general, see Glossary of chess; for a list of chess-related games, see List of chess variants.
The wolf, goat and cabbage problem is a river crossing puzzle. It dates back to at least the 9th century, and has entered the folklore of several cultures.
Rubik's Clock is a mechanical puzzle invented and patented by Christopher C. Wiggs and Christopher J. Taylor. The Hungarian sculptor and professor of architecture Ernő Rubik bought the patent from them to market the product under his name. It was first marketed in 1988.
The missionaries and cannibals problem, and the closely related jealous husbands problem, are classic river-crossing logic puzzles. The missionaries and cannibals problem is a well-known toy problem in artificial intelligence, where it was used by Saul Amarel as an example of problem representation.
A river crossing puzzle is a type of puzzle in which the object is to carry items from one river bank to another, usually in the fewest trips. The difficulty of the puzzle may arise from restrictions on which or how many items can be transported at the same time, or which or how many items may be safely left together. The setting may vary cosmetically, for example, by replacing the river by a bridge. The earliest known river-crossing problems occur in the manuscript Propositiones ad Acuendos Juvenes, traditionally said to be written by Alcuin. The earliest copies of this manuscript date from the 9th century; it contains three river-crossing problems, including the fox, goose and bag of beans puzzle and the jealous husbands problem.
Induction puzzles are logic puzzles, which are examples of multi-agent reasoning, where the solution evolves along with the principle of induction.
Geometry processing, or mesh processing, is an area of research that uses concepts from applied mathematics, computer science and engineering to design efficient algorithms for the acquisition, reconstruction, analysis, manipulation, simulation and transmission of complex 3D models. As the name implies, many of the concepts, data structures, and algorithms are directly analogous to signal processing and image processing. For example, where image smoothing might convolve an intensity signal with a blur kernel formed using the Laplace operator, geometric smoothing might be achieved by convolving a surface geometry with a blur kernel formed using the Laplace-Beltrami operator.
The dead-end elimination algorithm (DEE) is a method for minimizing a function over a discrete set of independent variables. The basic idea is to identify "dead ends", i.e., combinations of variables that are not necessary to define a global minimum because there is always a way of replacing such combination by a better or equivalent one. Then we can refrain from searching such combinations further. Hence, dead-end elimination is a mirror image of dynamic programming, in which "good" combinations are identified and explored further.
The five room puzzle is a classical, popular puzzle involving a large rectangle divided into five "rooms". The objective of the puzzle is to cross each "wall" of the diagram with a continuous line only once.
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises the travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which the first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy algorithm called the savings algorithm.
The Price of Anarchy (PoA) is a concept in economics and game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. It is a general notion that can be extended to diverse systems and notions of efficiency. For example, consider the system of transportation of a city and many agents trying to go from some initial location to a destination. Let efficiency in this case mean the average time for an agent to reach the destination. In the 'centralized' solution, a central authority can tell each agent which path to take in order to minimize the average travel time. In the 'decentralized' version, each agent chooses its own path. The Price of Anarchy measures the ratio between average travel time in the two cases.
The jeep problem, desert crossing problem or exploration problem is a mathematics problem in which a jeep must maximize the distance it can travel into a desert with a given quantity of fuel. The jeep can only carry a fixed and limited amount of fuel, but it can leave fuel and collect fuel at fuel dumps anywhere in the desert.
The Three-detector problem is a problem in traffic flow theory. Given is a homogeneous freeway and the vehicle counts at two detector stations. We seek the vehicle counts at some intermediate location. The method can be applied to incident detection and diagnosis by comparing the observed and predicted data, so a realistic solution to this problem is important. Newell G.F. proposed a simple method to solve this problem. In Newell's method, one gets the cumulative count curve (N-curve) of any intermediate location just by shifting the N-curves of the upstream and downstream detectors. Newell's method was developed before the variational theory of traffic flow was proposed to deal systematically with vehicle counts. This article shows how Newell's method fits in the context of variational theory.
The Magnetic Tower of Hanoi (MToH) puzzle is a variation of the classical Tower of Hanoi puzzle (ToH), where each disk has two distinct sides, for example, with different colors "red" and "blue". The rules of the MToH puzzle are the same as the rules of the original puzzle, with the added constraints that each disk is flipped as it is moved, and that two disks may not be placed one on another if their touching sides have the same color. Each disk has a North and South pole, with similar poles repelling one another and opposite poles attracting one another. Magnets inside each disk physically prevent illegal moves.
The Challenge: War of the Worlds is the thirty-third season of the MTV reality competition series The Challenge. This season featured alumni from The Real World, The Challenge, Are You the One?, The Bachelor Canada, The Bachelorette, Big Brother, Celebrity Big Brother UK, Love Island UK, Survivor Turkey, American Ninja Warrior, Party Down South, Geordie Shore, Ex on the Beach, Telemundo, and Floribama Shore competing for a share of a $1 million prize. The season had a "Basic Training" launch special on January 30, 2019, and premiered on February 6, 2019 on MTV.
