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.