Question

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

Answer 1

Тааакс,
1) Раб₁ и Раб₂ едут перебираются через реку
2) Раб₂ остается на другом берегу, а Раб₁ едет обратно
3) Раб₁ забирает Людоеда₁, переправляются и оба остаются 
4) Раб₂ едет и забирает Людоеда₂, оставляет Людоеда₂
5)  Раб₂ едет и забирает Раба₃, переправляются и остается Раб₂
6) Раб₃ едет за Людоедом₃ и оба переплывают реку

Answer 2

Если все 6 человек (3 людоеда и 3 слуги) попытаются переправиться на лодке одновременно, то как минимум один слуга окажется в отсутствии своего хозяина, и, согласно условию, будет съеден. Чтобы избежать этого, можно использовать следующую стратегию:

1. Сначала переправить одного людоеда на другой берег без его слуги.
2. Затем вернуться за первым слугой первого людоеда и переправить его на другой берег вместе со вторым людоедом, оставив первого людоеда на другом берегу.
3. Переправить второго слугу на другой берег без его хозяина.
4. Вернуться за первым людоедом и переправить его на другой берег вместе со вторым слугой, оставив второго людоеда на другом берегу.
5. Наконец, вернуться за последним людоедом и переправить его на другой берег вместе с оставшимся слугой.

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