Find two different solutions of the puzzle

Assignment Help Mathematics

Reference no: EM131177618

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?

Reference no: EM131177618

Questions Cloud

Statement in relation to project management : They are, effectively, "feeling each other out" and finding their way around how they might work together. Discuss this statement in relation to project management. 1000 words

Describe the ethical issues related to cultural competence : Examine the influence of your own personal values as related to the diversity issues presented in this case. Reflect on how you felt as you read the case study, how your values came into play, and how you would handle your values in a situation su..

Discuss this statement in relation to project management : They are not yet working on the project. They are, effectively, "feeling each other out" and finding their way around how they might work together. Discuss this statement in relation to project management. 1000 words

Determine the reorder point and safety stock : Determine the reorder point and safety stock that will achieve a 95 percent service level given a constant 2-day delivery lead time.

Find two different solutions of the puzzle : 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.

How the movie compare to our wall street big bankers today : A movie you will never forget-a true "classic"--managerial economics ethical or not/ including banking- a historical perspective. This film is all based on fact. It happened like you see it. How does this compare to our Wall Street big bankers tod..

Will the buyer succeed in recovering the excess : The buyer didn't commence action to recover the excess payment until some nine months after delivery. Will the buyer succeed in recovering the excess?

Determine whether directed graph shown has an euler circuit : Determine whether the directed graph shown has an Euler circuit. Construct an Euler circuit if one exists. If no Euler circuit exists, determine whether the directed graph has an Euler path. Construct an Euler path if one exists.

Discuss the application of strengths to the activity : Select one of the instruments from your research and complete the test to determine your strengths. Then do the following: Evaluate your results and create a list of your personal signature strengths.

User Account

All Pages