К берегу реки подошли три людоеда, у каждого из них по одному слуге. В присутствии хозяина его слугу никто не трогает, а в отсутствие хозяина его слугу съедают другие людоеды. Всем им надо перебраться на другой берег в двухместной лодке. Как сделать, чтобы никто никого не съел?

Обозначим людоедов как Л1, Л2, Л3, а их слуг соответственно С1, С2, С3. То есть Л1 — хозяин С1, Л2 — хозяин С2, Л3 — хозяин С3.

Важно соблюдать правило: слуга может находиться рядом с чужим людоедом только тогда, когда рядом находится и его собственный хозяин. Если же на берегу находятся только слуги, им ничего не угрожает.

Один из вариантов переправы:

1. Л1 и С1 переправляются на правый берег.

2. Л1 возвращается один.
   На правом берегу остаётся С1, но людоедов там нет, поэтому он в безопасности.

3. С2 и С3 переправляются на правый берег.
   Теперь справа находятся все три слуги, а людоедов там нет.

4. С1 возвращается на левый берег.
   Слева теперь Л1, Л2, Л3 и С1. С1 в безопасности, потому что его хозяин Л1 находится рядом.

5. Л2 и Л3 переправляются на правый берег.
   Слева остаются Л1 и С1, а справа — Л2, Л3, С2 и С3. У каждого слуги на обоих берегах его хозяин рядом.

6. Л3 и С3 возвращаются на левый берег.
   Слева оказываются Л1, С1, Л3, С3; справа — Л2 и С2. Всё безопасно.

7. Л1 и Л3 переправляются на правый берег.
   Слева остаются С1 и С3 — одни слуги, поэтому им ничего не грозит. Справа находятся все три людоеда и С2, причём хозяин С2 — Л2 — находится там же.

8. С2 возвращается на левый берег.
   Теперь слева находятся все три слуги, справа — все три людоеда.

9. С1 и С3 переправляются на правый берег.
   Справа их хозяева Л1 и Л3 присутствуют, поэтому оба защищены. Слева остаётся один С2.

10. С3 возвращается на левый берег.

11. С2 и С3 вместе переправляются на правый берег.

В результате на правом берегу оказываются Л1, Л2, Л3, С1, С2 и С3, и за всё время переправы ни один слуга не оставался с чужим людоедом без присутствия своего хозяина.