Acho que eu estava no ensino primário quando ouvi esta história pela primeira vez: um homem precisa atravessar o rio com uma onça, uma cabra e uma alface. Terá que fazer várias viagens porque o barco só permite que leve um passageiro de cada vez. Ele não pode deixar a onça sozinha com a cabra, nem a cabra sozinha com a alface: em qualquer desses casos, a primeira come a segunda. Como fazer?

Há uma variante ainda mais interessante deste problema, um jogo que chamarei "humanos e klingons" (o nome habitual é "missionários e canibais", mas está baseado em preconceitos culturais que não me agradam).

Três humanos e três klingons (espécie alienígena muito agressiva) precisam atravessar um rio, usando um barco no qual cabem no máximo dois passageiros. Se em algum momento os klingons forem maioria, em qualquer das margens, vão dominar os humanos e matá-los. Como fazer para transportar os seis para a outra margem, sem risco de massacre?

Brincadeiras como esta podem ser resolvidas matematicamente usando um conceito muito simples, chamado grafo. Um grafo é um conjunto de pontos, os vértices, alguns dos quais estão ligados por curvas, as arestas. Os vértices são usados para representar as diferentes situações do jogo, e as arestas para descrever as possíveis passagens de uma situação para a outra.

No caso de "humanos e klingons", cada situação pode ser descrita indicando o número H de humanos e o número K de klingons na margem direita, digamos (os demais estão na margem esquerda, não é necessário especificar). 

A tabela acima exibe todas as situações possíveis: são 10 vértices. Os retângulos em branco correspondem aos casos em que os klingons estariam em maioria, em uma das margens, e teríamos um massacre de humanos.

Também precisamos acrescentar as possíveis passagens de uma situação para outra, lembrando que o barco pode levar e trazer um ou dois passageiros. Isso está feito na tabela abaixo: são 17 arestas.

 Agora basta procurar neste grafo um caminho que vá dos pontos H=3 e K=3 (ambos na margem direita) para os pontos H=0 e K=0 (ambos na margem esquerda) e que esteja formado, alternadamente, por movimentos para a esquerda ou para baixo e movimentos para a direita ou para cima. Esta regra corresponde ao fato de que o barco se desloca, alternadamente, de uma margem para a outra.

Pode-se verificar que existem exatamente quatro soluções para o problema. Uma delas está representada na figura abaixo: são necessárias 11 viagens do barco, mas todos passam para a outra margem, sãos e salvos.