A group of n tourists must cross a wide and deep river with no bridge in sight. They notice two 13-year-old boys playing in a rowboat by the shore. The boat is so tiny, however, that it can only hold two boys or one tourist. How can the tourists get across the river and leave the boys in joint possession of the boat? How many times need the boat pass from shore to shore?

A group of n tourists must cross a wide and deep river with no bridge in sight. They notice two 13-year-old boys playing in a rowboat by the shore. The boat is so tiny, however, that it can only hold two boys or one tourist. How can the tourists get across the river and leave the boys in joint possession of the boat? How many times need the boat pass from shore to shore?

Operations Research : Applications and Algorithms

4th Edition

ISBN:9780534380588

Author:Wayne L. Winston

Publisher:Wayne L. Winston

Chapter19: Probabilistic Dynamic Programming

Section19.4: Further Examples Of Probabilistic Dynamic Programming Formulations

Problem 7P

See similar textbooks

Similar questions

On an island, a group of people are living until a visitor arrives with an odd directive: everyone with blue eyes must leave the island as quickly as possible. Every evening, a flight will depart at 8:00. Everyone can see the colour of everyone else's eyes, but they are blind to their own (nor is anyone allowed to tell them). They also do not know the number of persons who have blue eyes, but they do know that at least one person has them. How long will it take the folks with blue eyes to leave?
Three prisoners have been sentenced to long terms in prison, but due to over crowed conditions, one prisoner must be released. The warden devises a scheme to determine which prisoner is to be released. He tells the prisoners that he will blindfold them and then paint a red dot or blue dot on each forehead. After he paints the dots, he will remove the blindfolds, and a prisoner should raise his hand if he sees at least one red dot on the other two prisoners. The first prisoner to identify the color of the dot on his own forehead will be release. Of course, the prisoners agree to this. (What do they have to lose?) The warden blindfolds the prisoners, as promised, and then paints a red dot on the foreheads of all three prisoners. He removes the blindfolds and, since each prisoner sees a red dot (in fact two red dots), each prisoner raises his hand. Some time passes when one of the prisoners exclaims, "I know what color my dot is! It's red!" This prisoner is then released. Your problem…
A bandit with a weapon suddenly accosted a quaker as he walked along a remote road. "Your money or your life!" screamed the thief. Because I would be supporting thee in evildoing, my buddy said, "I cannot provide my money, but exchange is permissible, and I will offer thee my purse for the gun." He agreed to give it back, but he was threatened with gunfire, according to the thief, who claimed the quaker pulled a pistol at him and screamed, "Now buddy, give me back my wallet or I'll shoot you."
Mr Monkey is standing in front of a row of banana trees on Skull Island which actually belong to his rival King Kong. The banana trees are unusually high on that island. He wants to steal as many bananas as possible. Here is his plan. He will climb up one of the trees and then keep jumping from one tree to the immediately next one, while collecting all the bananas from each of them. But he will not switch the direction of his jumps. No longer being the agile young monkey he once used to be, he can only jump a total distance of L, after which he will climb down and run away before Kong crushes his head. Let the trees be labelled as t1, t2, ·.· tn. Let v;, Vi = 1, 2, · ..n be the number of bananas in tree t;. Further, let l;, i = 1,2, Can you write an algorithm to help Mr. Monkey steal as many bananas as possible ? Your algorithm should be a polynomial in n, L. Please show all the steps of DP as in the sample solution - subproblem definition, recurrences, pseudocode, runtime . (Statutory…
Suppose a business person launches new cinema at Islamabad and ask his team to develop a ticket system for box office. He assigns some requirements about system that how should it work. The requirements are such a way that there are only '5' number of box office windows in the theatre. Each window can have at max '20' number of people waiting in line. To start with, only one window is opened. If the number of people waiting in line in that window exceeds 20, then the next window is opened and people can join the line in that window. Likewise, if both the first and second windows have n number of people waiting in each queue, then a third window is opened. This can go on until the maximum number of windows w is reached. Let us assume that once a window is opened it never closes. A new window is only opened if all open windows are full. Each person can buy only one ticket. So, the system should not allot more than one ticket per person. Let us assume that the system issues one ticket…
Q:With the advancement in technology, computer related crimes are taking birth rapidly. One day, a hacker stole the data from one of the computers being used in the bank and transferred confidential information to the opponents. After detectors found the criminal, all became surprised as he was no other but the assistant manager of the same bank. Keeping the scenario in mind, enlist all the reasons behind this immoral act and propose some suggestions to overcome such acts.
One out of a thousand soda cups you have is poisonous. You have ten test samples that you can use to look for poison. A single drop of poison will forever mark the test strip as positive.A test strip may have any number of droplets applied at once, and it may be used again and again (as long as the results are negative). Tests can only be performed once per day, and results don't come back for seven days. How could you identify the poisoned container in the shortest amount of time?A follow-up Create software to practise your strategy.
The Youth Bowling Clubs Association (YBCA) is a loose group of children’s ten-pin bowling clubs that compete with inter-club competitions regularly throughout the year. It is run on an amateur basis, and each week volunteers from each of the clubs present at a competition provide a referee and scorer for the competition. As the clubs are affiliated with bowling alleys, each club takes it in turns to host the competitions, and there is a rule that no club can have a scorer or referee at a competition they are participating in. The Managing Committee of the YBCA have been organising the competitions informally for many years, and now want to put the officiating on a formal basis, which will be auditable by the Australian Bowling Association (ABA). They have passed a set of by-laws, and to ensure that the process works properly, and is fair, they have decided to commission a computer system – Official-Eze. The Committee wants the Official-Eze system to automate the process of…
a) Explain on Simulated Annealing algorithm behaves at very high temperatures, and how it behaves at very low temperatures. (b) Imagine the implementation of Simulated Annealing algorithm in real life. Let's say, you have a caretaker at your home. Your home has a garden and it has a fountain with a network of pipes that contains 150 faucets. You informed your caretaker that you are going for short holiday to Langkawi for 3 days and when you return you would like the fountain to spray as high as possible. Your caretaker knows that it is impossible to check all faucets within 3 days to obtain an optimal setting. You can use Simulated Annealing algorithm to maximize the height of the fountain, also can assume whether a faucet can be ON or OFF and measuring the water height. Adding to that, you can make any other assumptions required for this scenario, explain clearly using Simulated Annealing algorithm.
There are N light bulbs numbered 1 to N, all kept off initially. There are also N persons who will toggle all the bulbs. The first person comes and toggles all the bulbs. The second person comes and toggles all even bulbs. The third person comes and toggles all multiples of 3. This process continues till all N persons pass. When N=16, only the bulbs 1,4,9, and 16 are on. When N=50, how many bulbs are on?
Deep in the forest of Hanoi there is a temple with three large pillars. At the beginning of time there were N golden disks placed on the Easternmost pillar. Each disk has a distinct radius. The disks were stacked from top to bottom in increasing order of radii. Note: the disks are too fragile to have a larger radi disk on top of a smaller one. Everyday since the beginning of time the monks of the temple have moved exactly one disk from a pillar to another. Since the disks are heavy and there are not that many monks, at most one disk is off a pillar at a time. Disks can only be removed from the top of a pillar. Rumor has it that when all the disks are on the Westernmost pilar the world is supposed to end. The monks are very logical and wish to stop moving disks around, so you can assume that they will make the sequence of moves that will end the world as fast as possible. Dr. Meade has 36 days in each of his months. Travis is sure time began on the first of some month. On which of the…
Legend has it that during the Jewish-Roman battle, the first-century Jewish historian Flavius Josephus was taken prisoner among a group of 40 other Jews. The captive troops made a decision to commit suicide rather than be caught and made plans to do so. To kill every third soldier until they were all dead, they were to surround the enemy in a circle. When Joseph and one other person decided they didn't want to participate, they rapidly calculated where they needed to be in the circle for survival. Create a software that enables you to put n persons in a circle and tell it to murder every m of them. The final individual in the circle should be identified by number by the software.