# River Crossings

- Combining
**story telling**with preposterous scenarios (and the potential to create your own) makes for a great problem for engaging students. - As students reason through the possible solutions, they develop their
**communication**and**logical reasoning**skills. - The activity is low-floor in that every student can get started by the simple act of trying something, yet gets progressively more difficult.
- Students are naturally pushed towards developing their own
**notation**structures that help them strategize and discover**patterns**.

**Why do YOU like this activity? Try it out and let us know at info@jrmf.org!**

**
Make sense of problems and persevere in solving them.
**ccss.math.practice.mp1

River crossings is a low-floor problem, in that any student can get started by the simple act of trying something and seeing what happens. And then trying something else. This allows the student to focus on the mathematical process and helps develop the problem-solving skill of looking ahead, which is the ability to anticipate the results of the next few steps. From there, the students can start thinking about the solution as a pathway and think about what might hinder or help their progress. And when they successfully solve one problem, there is always another problem to challenge and engage them.

Construct viable arguments and critique the reasoning of others.

ccss.math.practice.mp3

This activity is great for getting students to explain their thinking because it’s framed as a story. This provides starting points for their arguments like “We need to bring the wolf, because…” or “We can’t leave the cabbage, because three moves from now…”, which encourages them to practice their mathematical communication skills.

Model with mathematics.

ccss.math.practice.mp4

This idea of working with constraints is an important idea in mathematics and river crossing puzzles make readily apparent the need to develop an organized and readable way of representing them. This notation will vary between students but they should be encouraged to develop some kind of tracking system that makes sense to them. It will also help with logical reasoning as well as students explain their model.

**
Look for and make use of structure.
**ccss.math.practice.mp7

Tracking their moves helps here as students may recognize cases or dead ends they have already encountered. This helps them move from trial and error and into sense-making and pattern recognition. It provides the tool to help them reason through more challenging problems.

**Problem History**

River crossing puzzles are a genre of logic puzzles often attributed to Alcuin of York (735-804) although versions of this puzzle have been found throughout Europe and Africa. In our sequences, we have retained two of the classics – wolf-goat-cabbage and adult-child puzzles – and added two more. *Zombies and Humans* is our spin on the dated cannibal-missionary puzzles and *Monsters* is our fun, novel puzzle that adds an arithmetic aspect.

**Mathematical Theory**

**State Transition Graphs**

At the heart of every river crossing puzzle is a collection of legal arrangements (or states) and transitions from one state to another. A natural way to represent a puzzle is as a **graph**, taking these states as **vertices** and transitions as **edges**. In the classic wolf-goat-cabbage puzzle, there are 16 possible states, divided into legal and illegal:

**Legal**

**Illegal**

We can then examine the 10 legal states and diagram the possible transitions:

The far left vertex is the starting state and the far right is the desired end state, so solving the puzzle now amounts to finding a path from the start to end following the edges. We can see there are two shortest paths (the upper path and the lower path), each requiring 7 crossings.

**Vertex Covers**

In a generalized version of the wolf-goat-cabbage problem, imagine that you have a large collection of objects where each pair can either be left together unsupervised or not. If there are *n* objects, then the puzzle can always be solved if there are *n* spaces in the boat, since the ferry person can keep an eye on all of them with a single trip. However, the puzzle may not be solvable if the boat only has room for a single item. There is a smallest boat that can be used to solve the puzzle, and the number of items this boat can ferry is called the **Alcuin number.** By the above discussion, the Alcuin number is always between 1 and *n*, inclusive.

**For more details on the history and theory behind River Crossings puzzles, see ****here****!**