Difficulty: Medium, Asked-In: Google, Microsoft
A group of four people, who have one torch, need to cross a bridge at night. A maximum of two people can cross the bridge at one time, and any pair that crosses (either one or two people) must have the torch with them. The torch must be walked back and forth and cannot be thrown. Person A takes 1 minute to cross the bridge, person B takes 2 minutes, person C takes 5 minutes, and person D takes 10 minutes. A pair must walk together at the rate of the slower person’s pace. Find the fastest way they can accomplish this task.
Here we need to consider the following constraints:
So total time to cross the bridge will be the summation of the time taken to cross the bridge and the time taken by people to return with the torch. To find the shortest time, we need to minimize the time to cross the bridge and return time. Now during return, the person who takes the minimum time to cross the bridge would be the obvious choice.
To design a solution for this problem, three two-person trips and two one-person trips are needed for four people to get to the other side in a minimum amount of time. If the flashlight is returned by the fastest person on both back trips, the fastest person will have to participate in each pair going to the other side, for the total time of 2 + (1 + 10) + (1 + 5) = 19 minutes.
In the above strategy, both slowest persons make a separate trip with the fastest person and take a total of 15 minutes combined. Can we think about reducing the time here? Can we think of sending the slowest people together? Insight is: the difference between the fastest people (1 and 2 minutes) is just 1 minute but the difference between the slowest people (5 and 10 minutes) is 5 minutes.
Suppose one of the two back trips is not made by the fastest person. In other words, let's try the second best possibility: one back trip of the fastest person (1 minute) and one back trip of the second-fastest person (2 minutes). The return crossing times will be at least 1 + 2 = 3 minutes i.e. 1-minute return trip for the fastest person and 2 minutes return trip for the second-fastest person.
Trips to the other side will be at least 2 + 10 + 2 = 14 minutes because the pair of slowest people (5, 10) will take 10 minutes to cross the bridge. At the same time, the other two pairs, i.e. the first and last trip of pairs (1, 2), will take at least 2 minutes each. Therefore, the total crossing time will take at least 17 minutes.
Another insight: Person A and B can cross the bridge together, and A can return back with the torch. Now we have a choice to select two people out of A(1), C(5), and D(10). We want to reduce the time taken by the slowest person C & D here, and we already have a faster person B on the other side. So we can send C and D together, and B can return back with the torch. Now A and B can cross the bridge with the torch. Total time to cross the bridge = (A + B) + A + (C + D) + B + (A + B) = B + A + D + B + B = A + 3B + D = 17 Minutes
The Königsberg Bridges Problem: is it possible, in a single traversal, to cross all seven bridges exactly once and return to the starting point? The figure shows a sketch of the river with its two islands and seven bridges.
Ferrying Soldiers: A detachment of 25 soldiers must cross a broad and deep river with no bridge in sight. They notice two 12-year-old boys playing in a rowboat by the shore. However, the boat is so tiny that it can only hold two boys or one soldier. How can the soldiers get across the river and leave the boys in joint possession of the boat? How many times does the boat pass from shore to shore in your algorithm?
Two Jealous Husbands: Two married couples need to cross a river. They have a boat that can hold no more than two people at a time. To complicate matters, both husbands are jealous and require that no wife can be in the other man's presence without her husband being present. Can they cross the river under such constraints?
A Wolf, a Goat, and a Cabbage: A man finds himself on a riverbank with a wolf, a goat, and a head of cabbage. He needs to transport all three to the other side of the river in his boat. However, the boat has room for only the man himself and one other item (either the wolf, the goat, or the cabbage). In his absence, the wolf would eat the goat, and the goat would eat the cabbage. Show how the man can get all these “passengers” to the other side.
Missionaries and Cannibals: Three missionaries and three cannibals must cross a river. Their boat can only hold two people, and it cannot cross the river by itself with no people on board. Each missionary and each cannibal can row the boat. If present, missionaries cannot be outnumbered by cannibals. How can all six get across the river with the fewest crossings?
Reference: Algorithmic Puzzles by Anany Levitin and Maria Levitin
Enjoy learning, Enjoy mathematics!
There are 3 doors behind which are two goats and a car. You pick door 1 hoping for the car but don’t open it right away. Monty Hall, the game show host who knows what's behind the doors, opens door 3, which has a goat. Here's the game: do you want to pick door No. 2? Is it to your advantage to switch your choice?
You’ve got someone working for you for seven days and a gold bar to pay him. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. What is the fewest number of cuts to the bar of gold that will allow you to pay him 1/7th each day?
You have given n-bulbs connected in a circle with a switch for each bulb. The connection is such that if you change the state of anyone bulb may be on or off, it will toggle the state of its adjacent bulbs. All the bulbs are initially switched off. You have to find the number of steps such that all the bulbs are switched on.