Em uma margem de um rio estão um leão, um coelho e um pé de alface. A canoa pode levar apenas você e mais um objeto. Por algum motivo inexplicável da natureza, se você levar o pé de alface, o leão come o coelho. Se você levar o leão, o coelho come o pé de alface. Como fazer para transportar todos em segurança para a outra margem do rio?
Passo 1
A gente tem um rio onde estão na margem inicial um leão, um coelho e um pé de alface, e uma canoa que só leva você mais um item por vez. As regras de segurança são: sem você por perto, o leão come o coelho; e sem você por perto, o coelho come a alface. O conteúdo aqui é modelar estados seguros e usar uma sequência de travessias pra nunca deixar um par perigoso sozinho.
Passo 2
Como primeiro movimento, nós levamos o coelho para a outra margem. Assim, na margem inicial ficam leão e alface (que é seguro), e na margem oposta fica o coelho.
Voltamos sozinho para a margem inicial, pegamos o leão e atravessamos. Na margem oposta ficam leão e alface? Não: antes de deixar o leão lá, trazemos o coelho de volta para evitar que o leão o coma. Então nessa viagem garantimos que sempre alguém impeça o ataque.
Voltamos sozinho para a margem inicial, pegamos o leão e atravessamos. Na margem oposta ficam leão e alface? Não: antes de deixar o leão lá, trazemos o coelho de volta para evitar que o leão o coma. Então nessa viagem garantimos que sempre alguém impeça o ataque.
Passo 3
Agora na margem inicial estão coelho e alface (que é perigoso), mas ainda estamos lá, então antes de deixá-los sozinhos levamos o coelho para a margem oposta. Desta forma sobram só alface e leão na margem inicial, o que é seguro.
Passo 4
Por fim, voltamos de novo sozinho para buscar o coelho na margem inicial e o levamos definitivamente para a margem oposta. Em cada etapa, verificamos os pares perigosos e nunca deixamos leão e coelho juntos nem coelho e alface juntos sem nossa presença.
Resposta
- Levar o coelho para a outra margem
- Voltar sozinho
- Levar o leão para a outra margem e, antes de deixá-lo, trazer o coelho de volta
- Levar a alface para a outra margem
- Voltar sozinho
- Levar o coelho de novo para a outra margem