The Incompatible Cargo

Question

A courier must ferry a falcon, a rabbit, and a crate of lettuce across a river in a boat that holds her plus one item. Left alone together (without her), the falcon attacks the rabbit, and the rabbit eats the lettuce. Falcon and lettuce coexist peacefully. What is the minimum number of one-way crossings to get everything across safely?

Accepted Answer

Seven crossings. 1. Take the rabbit over. 2. Return empty. 3. Take the falcon over. 4. Bring the rabbit back. 5. Take the lettuce over. 6. Return empty. 7. Take the rabbit over. Why the rabbit must move first: the rabbit conflicts with both other items, so the only safe pair to leave alone is falcon + lettuce, which means the first trip carries the rabbit, forced. The non-obvious move is step 4: ferrying something backward. Progress isn't monotone; the state "falcon and rabbit both across, courier leaving" is illegal, so the rabbit shuttles home to chaperone-swap. Why 7 is minimal: each round trip (over and back) nets at most one item across, and the final trip nets one more. Getting 3 items across therefore needs at least 2 cdot 3 + 1 = 7 one-way crossings given that some return trip must carry cargo; more carefully, a breadth-first search of the 16 safe states confirms no 5-crossing solution exists, the backward-rabbit detour is unavoidable because both "rabbit across alone" follow-ups strand a conflict. The interview point is small but real: when a constraint graph has one vertex conflicting with everything (the rabbit), schedule around that vertex, and don't assume optimal plan

The Incompatible Cargo

Problem

Your answer

Hints