Grafos permitem entender a matemática por trás dos jogos
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). É possível jogar on-line aqui.
Leia também: OBM 2017 divulga vencedores e anuncia testes para o time Brasil
OBMEP inspira e capacita professores
Pesquisador do IMPA ganha bolsa do Serrapilheira
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.
Para ler o texto na íntegra acesse o site do jornal:
