Send to a Friend

LostInParadise's avatar

Does this explanation related to recreational mathematics river crossing problems make sense?

Asked by LostInParadise (31926points) August 13th, 2023

There are a number of recreational math problems involving the use of a boat to transfer a group from one side of a river to the other side. I have noticed a simple feature that is common to many of these problems that I have never seen anyone discuss. As an example, I am going to use the cannibal and missionary problem.

There are 3 cannibals and 3 missionaries that are to cross the river using a boat. At most 2 people can fit in the boat and the missionaries on either shore cannot be outnumbered by the cannibals, but you can have cannibals on either shore with no missionaries.

There are two aspects to this problem, which when combined creates an interesting effect.

Firstly, imagine filming a solution to this problem. Then imagine showing the film in reverse. The movement from final position to initial position is legal.

Secondly consider the concept of the complement of a position. If we denote a position as (A,B) where A is the population on the near shore and B is the population on the far shore then the complement of (A,B) is (B,A). In particular, the complement of the initial position is the final position.

Now suppose that in working on this problem, you get to a case where the next position is the complement of the previous one. Spoiler alert – For the cannibal and missionary problem, you get to a point where there are 2 cannibals and missionaries on one side and one cannibal and one missionary on the other side. If the side with two of each ships across one of each, the position reached is the complement of the previous one.

Now we put everything together. If we go backwards from the next to the last position, we reach the first position. Starting from the complented position, we can arrange things so that each of the positions going in reverse are all complements of the first reversed sequence. In particular, the last position reached going backwards is the complement of the initial position, and is therefore a solution to the problem.

Using Fluther

or

Using Email

Separate multiple emails with commas.
We’ll only use these emails for this message.