The Scenario
Three IT security analysts and three hackers are travelling together. Each analyst is carrying a flash drive containing incredibly sensitive passwords that the hackers would very much like to steal.
As they travel, they reach a river they need to cross. The only way across is a raft that can hold at most two people at a time.
The Rules
- The raft cannot cross by itself — at least one person must be on board to row.
-
On either bank of the river, the analysts must never be outnumbered
by hackers. If hackers outnumber analysts, the hackers will steal the flash drives.
More precisely:
- N analysts can hold off N hackers, but not N+1 hackers (where N is a positive integer).
- A bank with no analysts is safe regardless of how many hackers are there — there are no flash drives to steal.
- When the raft pulls up to a bank, it is considered to be on that bank — even if a passenger stays on board and immediately rows back. This matters: if one analyst is alone on a bank and the raft arrives with two hackers on it, that analyst is in danger even if only one hacker steps off.
Your Task
Search for a sequence of raft trips that gets all six people safely across the river.
Work through this on paper first. Try to keep track of who is on each bank and where the raft is after every crossing. You may find it helpful to write down the state after each move — for example, using a notation like (analysts on left, hackers on left, raft position) to record where everyone is.
Do not worry if you get stuck or have to backtrack. Getting stuck is part of the point. Notice what it feels like to run into a dead end and have to reconsider your approach.
Variation — A Bigger Group, a Bigger Raft
Once you have solved the original problem, try this harder version:
Suppose there are five analysts and five hackers (ten people total), and the raft can now hold three passengers at a time. In this variation, the raft has the same constraint as the banks: a raft carrying one analyst and two hackers is illegal, because the analyst would be outnumbered on board.
How can you get all ten people across safely?
Before You Move On
After working through the puzzle — whether you solved it, got partway, or got thoroughly stuck — take a moment to reflect on the experience before reading on.
- What did you keep track of as you worked? Did you write anything down?
- When you hit a dead end, how did you decide where to back up to?
- Did you ever find yourself exploring the same situation twice?
- Did you develop any intuitions about which moves seemed more promising than others?
The readings in Topic 6b will give names and structure to exactly what you just experienced. You were doing a form of search — and the way you searched has a lot in common with the algorithms we will study.