Posted by: khuang01 | November 2, 2008

Crossing the River, Expanded

Most of us were given a basic problem some time in high school about transporting stuff across a river.  The problem usually goes something like this:

You’re standing on a river bank and you have a wolf, a sheep, and a sack of grain that you need to get to the other side.  You can only take one thing across at a time.  If you leave the wolf and sheep alone, or the sheep and grain alone, then something will get eaten.  How do you get everything across safely?

There is both an interesting cultural and mathematical background to this problem.

Culturally, “crossing the river” problems have been around for more than 1100 years and have equivalent recitations in most major cultures.  For instance, an African equivalent of the problem would feature a Jackal, Goat, and Fig Leaves.  Another version, more popular around the time of imperial expansion, involves 3 missionaries and 3 cannibals, where you can transport 2 people on the raft at any given time but the number of cannibals cannot exceed the number of missionaries at any given point.  This type of problem is even rumored to be given as a basic IQ test in certain Chinese job applications, but with a larger number of items.  You can find a flash game about it here.  You can already read more about the cultural background of the riddle here.

The interesting mathematical heritage is that these problems can only be solved in general using graph theory or dynamic programming.

With dynamic programming (wikipedia article here) you provide a computational answer through a more-efficient, but still brute-force method.  It involves breaking down the problem from the end-state and working backwards.  For example, in the very first example talked about above, you would first say: “Okay, I have to bring one animal across last, which one must it be?”  Knowing that the last one cannot be the wolf (otherwise the sheep and grain are alone at the end) and cannot be the grain (otherwise the wolf and sheep are alone at the end) then it must be that you bring the sheep across last.  You then repeat, working backwards, until you reach the beginning.  You can read an academic paper about dynamic programming solutions to river-crossing problems here.

With graph theory, things get even more interesting.  You can imagine that every possible combination of items divded between the two sides as a “state” or “node.”  So if you have n items you can have 2*(1 + nC1 + nC2 + nC3 + … + nCn) different states, each term in the sum representing a different number of items on the opposite bank (e.g. nC2 is the number of different sets of two items I can have on the opposite bank), and multiplying by “2” to represent that my raft can start at either bank.  Each node is connected to “n” other nodes (because you can switch the banks of any 1 of the items next term).  Based on whatever “rules” the riddle supplies to you, you then knock out whatever nodes are illegal.  And then anything that traces from your starting position to your ending position is a valid solution to the problem!  You can read an academic paper on the graphical solution to this problem here.

Thus, if you ever find yourself in a tricky situation with needing to cross a river, never fear!  Math has a solution for you.

Advertisements

Responses

  1. Quite an interesting post! I like the graph theory visual approach. It seems that graph theory can be used to approach a lot of hard computational problems. I wonder if there are mathematical, non-computational solutions to some simpler instances of this problem? This problem has a lot of conditions (who can’t be left with who in a boat or on a bank), so I’m not sure what the ‘simplest’ version of it would be.

  2. I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. In fact your creative writing abilities has inspired me to start my own Blog Engine blog now.

    reflective essay

  3. Funny you mention this equation. This problem could solve the magnetic motor theory for so many, instead they only see the wolf and the sheep without examining the rest of how it works. I remember this problem from when I was 5. Guess most people aren’t Einsteins. That’s probably a good thing. After all, look what he did. What a jack ass. Tesla was right. Einstein had the present, but the future was his. It’s a shame, Tesla sounds like he was an interesting dude. I could have shown him things that would make him shit. For example, the second law of thermodynamics doesn’t apply when it comes to magnatism, circles, and the third ingredient, which seems to elude the most brilliant of educated morons. Perhaps they should ask the navigator to take control of the ship. Instead they let the cook, who poked his eye out with a fork because he’s a clumsy useless double talking idiot. Welcome to the age of stupid!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: