Reference no: EM131167275
Use a graph model and a path in your graph, as in Exercise 64, to solve the jealous husbands problem. Two married couples, each a husband and a wife, want to cross a river. They can only use a boat that can carry one or two people from one shore to the other shore. Each husband is extremely jealous and is not willing to leave his wife with the other husband, either in the boat or on shore. How can these four people reach the opposite shore?
Exercise 64
In an old puzzle attributed to Alcuin ofYork (735-804), a farmer needs to carry a wolf, a goat, and a cabbage across a river. The farmer only has a small boat, which can carry the farmer and only one object (an animal or a vegetable). He can cross the river repeatedly. However, if the farmer is on the other shore, the wolf will eat the goat, and, similarly, the goat will eat the cabbage. We can describe each state by listing what is on each shore. For example, we can use the pair (FG,WC) for the state where the farmer and goat are on the first shore and the wolf and cabbage are on the other shore.
a) Find all allowable states of the puzzle, where neither the wolf and the goat nor the goat and the cabbage are left on the same shore without the farmer.
b) Construct a graph such that each vertex of this graph represents an allowable state and the vertices representing two allowable states are connected by an edge if it is possible to move from one state to the other using one trip of the boat.
c) Explain why finding a path from the vertex representing (FWGC, ∅) to the vertex representing (∅, FWGC) solves the puzzle.
d) Find two different solutions of the puzzle, each using seven crossings.
e) Suppose that the farmer must pay a toll of one dollar whenever he crosses the river with an animal. Which solution of the puzzle should the farmer use to pay the least total toll?
About high rates of unemployment
: The government is concerned about high rates of unemployment. To spark hiring, it provides tax incentives for the businesses to invest in new capital projects and stimulate job growth. If the sole concern is adding jobs, use the Hicks-Marshall rules ..
|
What is the elasticity of demand over the price
: What is the elasticity of demand over the price range $60 to $80
|
Determine whether the given graph has an euler circuit
: Determine whether the given graph has an Euler circuit. Construct such a circuit when one exists. If no Euler circuit exists, determine whether the graph has an Euler path and construct such a path if one exists.
|
The probability that his on base percentage will be less
: What is the probability that his on-base percentage will be less than 0.360? - What is the probability that his on-base percentage will be greater than 0.370?
|
Find two different solutions of the puzzle
: Explain why finding a path from the vertex representing (FWGC, ∅) to the vertex representing (∅, FWGC) solves the puzzle. d) Find two different solutions of the puzzle, each using seven crossings. e) Suppose that the farmer must pay a toll of one ..
|
What is this manufacturer fixed cost
: What is this manufacturer's fixed cost? For each level of output, calculate the variable cost (VC). For each level of output except zero output, calculate the average variable cost (AVC), average total cost (ATC), and average fixed cost (AFC)
|
Find the two probabilities
: A stock's current price is $80 per share. --- Find these two probabilities. How do they compare to one another?-
|
Concerned about high rates of unemployment
: The government is concerned about high rates of unemployment. To spark hiring, it provides tax incentives for the businesses to invest in new capital projects and stimulate job growth. If the sole concern is adding jobs, use the Hicks-Marshall rules ..
|
What would be the responsibility of a frontline manager
: Sam, a marketing manager, often makes ethical decisions based on what others feel about those decisions. He often considers opinions from other managers and employees. Which of the following ethical systems do Sam's decisions follow?
|