Farmer Crossing a RiverDate: 09/24/2001 at 02:50:17 From: Bobby Subject: The River Problem A farmer is taking his prize lettuce, lion, llama, and pet leviathan (a unique creature that eats llamas and lions unless a lettuce is present) to market. A boat awaits him to cross a river, but he can only take one item at a time. How can the farmer cross the river, without the llama eating the lettuce, the lion eating the llama, and the leviathan eating the llama and the lion? Date: 09/24/2001 at 13:43:33 From: Doctor Ian Subject: Re: The River Problem Hi Bobby, We begin with everything on one side of the river: ((far let lio lla lev) ()) The first interior ()'s indicate things on one side of the river, the second ()'s indicate things on the other side. At the end, we have everything on the other side of the river: (() (far let lio lla lev)) We need to connect these two states with a series of transformations, each of which involves moving the farmer and zero or on other things to the side opposite where he is at the moment. For example, here are all the possible transitions from the initial state: ((far let lio lla lev) ()) | +-> ((let lio lla lev) (far)) | +-> ((lio lla lev) (far let)) | +-> ((let lla lev) (far lio)) | +-> ((let lio lev) (far lla)) | +-> ((let lio lla) (far lev)) Note that some of these states are not legal. For example, if he takes the lettuce over, the leviathan is left alone with the lion and the llama. In fact, when we look closely, we see that most of the states are not legal. ((far let lio lla lev) ()) | +-> ((let lio lla lev) (far)) No: lla eats let | +-> ((lio lla lev) (far let)) No: lev eats lio, lla | +-> ((let lla lev) (far lio)) No: lla eats let | +-> ((let lio lev) (far lla)) Okay | +-> ((let lio lla) (far lev)) No: lio eats lla So now we can do the same thing, starting from the only possible state: ((far let lio lla lev) ()) | +-> ((let lio lla lev) (far)) No: lla eats let | +-> ((lio lla lev) (far let)) No: lev eats lio, lla | +-> ((let lla lev) (far lio)) No: lla eats let | +-> ((let lio lev) (far lla)) Okay | | | +-> ((let lio lev far) (lla)) Okay. | +-> ((let lio lla) (far lev)) No: lio eats lla Note that we can ignore states that duplicate previous states. (Do you see why?) So we don't have to consider the farmer bringing the llama back across the river with him. You can continue doing this, ((far let lio lla lev) ()) | +-> ((let lio lla lev) (far)) No: lla eats let | +-> ((lio lla lev) (far let)) No: lev eats lio, lla | +-> ((let lla lev) (far lio)) No: lla eats let | +-> ((let lio lev) (far lla)) Okay | | | +-> ((let lio lev far) (lla)) Okay. | | | +-> ((lio lev) (far let lla)) No: lev eats lio | | | +-> ((let lev) (far lio lla)) Okay. | | | + ... | +-> ((let lio lla) (far lev)) No: lio eats lla and eventually one of two things will happen. Either you'll get to the point where _all_ the possible transformations go back to previously explored states, in which case no solution is possible. Or you'll find that one of the legally reachable states has everything on the other side of the river, in which case you've found a solution to the problem. Note that there may be solutions that involve splitting the lettuce, although it's not clear that the person who made up the puzzle would accept them. I hope this helps. Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Ian, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/