Results 1 to 3 of 3

Math Help - Puzzle

  1. #1
    Junior Member
    Joined
    Mar 2007
    Posts
    34

    Puzzle

    A farmer needs to carry a wolf, goat, and a cabbage across a river. He has only one 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. [ The symbo 0 is used when nothing is on a shore, so that (FWGC,0) is the initial state ]


    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. Find 2 different solutions of the puzzle, each using seven crossings.

    Help? please
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,707
    Thanks
    627
    Hello, smoothi963!

    This is a classic (old) puzzle,
    . . but with a graph/network approach.


    A farmer needs to carry a wolf, goat, and a cabbage across a river.
    He has only one small boat, which can carry the farmer and only one object.
    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.
    [The symbol 0 is used when nothing is on a shore, so that (FWGC | 0) is the initial state.]

    (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) Find 2 different solutions of the puzzle, each using seven crossings.
    (a) .Each of the four objects {F, W, G, C} can be on the first shore or the other shore.
    Hence, there are: . 2^4 = 16 possible states.

    But the farmer must not be alone: . (F\,|\,WGC),\:(WGC\,|\,F)
    . . The wolf and goat must not be alone: . (WG\,|\,FC),\:(FC\ |\ WG)
    . . The goat and cabbage must be alone: . (GC\,|\,FW),\:(FW\,|\,GC)
    Hence, there are six states not allowed.

    Therefore: there are ten allowable states:

    . . (FWGC\,|\,0),\;(WC\,|\,FG),\;(FWC\,|\,G),\;(W\,|\,  FGC),\;(FWG\,|\,C)

    . . (C\,|\,FWG),\;(FGC\,|\,W),\;(G\,|\,FWC),\;(FG\,|\,  WC),\;(0\,|\,FWGC)


    (b) and (c) .The two graphs are:

    \begin{array}{ccccc} & & (FWGC\,|\,0) & & \\<br />
& & \downarrow & & \\<br />
& & (WC\,|\,FG) & &  \\<br />
& & \downarrow & & \\<br />
& & (FWC\,|\,G) \\<br />
& \swarrow & & \searrow & \\<br />
(W\,|\,FGC) & & & & (C\,|\,FWG) \\<br />
\downarrow & & & & \downarrow \\<br />
(FWG\,|\,C) & & & & (FGC\,|\,W) \\<br />
& \searrow & & \swarrow & \end{array}
    . . . . . . . . . . . \begin{array}{c}(G\ |\ FWC)\\<br />
\downarrow \\<br />
(FG\ |\ WC) \\<br />
\downarrow \\<br />
(0\ |\ FWGC)<br />
\end{array}

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2007
    Posts
    34
    lol this puzzle is awesome, i ended up solving it last night, but thank you so much. i looked over yours to make sure iw as correct. Math is fun when it comes to these types of problems. Thank you once again
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Set Puzzle
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 6th 2008, 07:46 AM
  2. new puzzle
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: October 10th 2007, 04:10 PM
  3. Puzzle
    Posted in the Math Challenge Problems Forum
    Replies: 3
    Last Post: December 22nd 2006, 03:38 PM
  4. A puzzle
    Posted in the Math Challenge Problems Forum
    Replies: 4
    Last Post: December 9th 2006, 07:40 PM
  5. more puzzle
    Posted in the Math Challenge Problems Forum
    Replies: 15
    Last Post: October 11th 2006, 08:26 PM

Search Tags


/mathhelpforum @mathhelpforum