Três jesuítas e três canibais precisam atravessar um rio; para tal, dispõem de um barco com capacidade para duas pessoas. Por medida de segurança, não se deve permitir que em alguma margem a quantidade de jesuítas seja inferior à de canibais. Qual a solução para efetuar a travessia com segurança? Elabore um algoritmo mostrando a resposta, indicando as ações que concretizam a solução deste problema.

Estando todos na margem A, a primeira travessia do barco será feita com um jesuíta levando um canibal para a margem B desse mesmo rio:

Com o canibal na margem B, o próximo passo do algoritmo é:

Já na margem A, com três jesuítas e dois canibais presentes, existem as seguinte possibilidades:

1. A travessia de A para B ser feita por um canibal e um jesuíta, nesse caso a margem B se torna insegura para o jesuíta;
2. A travessia de A para B ser feita por dois jesuítas, nesse caso a margem A se torna insegura para o jesuíta remanescente.

Dessa forma, a travessia do barco da margem A para a margem B deve ser feita por dois canibais:

Com o canibal na margem B, o próximo passo do algoritmo é:

Já na margem A, com três jesuítas e apenas um canibal presentes, existe a seguintes possibilidade de travessia:

1. A travessia de A para B ser feita por um canibal e um jesuíta, nesse caso a margem B se torna insegura para o jesuíta.

Sendo assim, a travessia do barco da margem A para a margem B deve ser feita por dois jesuítas:

Com um dos jesuítas na margem B, o seu amigo jesuíta não pode voltar sozinho para a margem A, pois a margem B se tornaria insegura para o jesuíta deixado. Com isso, o próximo passo do algoritmo é:

Na margem A, com dois jesuítas e dois canibais presentes, existem as seguintes possibilidades de travessia:

1. A travessia de A para B ser feita por um canibal e um jesuíta, nenhuma das margens se torna instantaneamente um insegura (mas confia em mim, os retornos se tornam extremamente complicados devido ao espalhamento entre canibais e jesuítas);
2. A travessia de A para B ser feita por dois canibais, nesse caso a margem B se tornaria um perigo para o jesuíta presente lá.

Dessa forma, a travessia do barco da margem A para a margem B deve ser feita por dois jesuítas:

Na margem B, com os três jesuítas e um canibal presentes, o algoritmo se torna praticamente solucionado.

Uma vez que os três jesuítas já se encontram na margem B, o canibal presente nessa mesma margem pode ser o realizador das travessias que irão buscar os dois canibais remanescentes na margem A, dessa forma os próximos passos do algoritmo serão:

Pronto, agora todos estão em segurança na margem B do rio!