dados três baldes, um cheio com oito litros de água, e dois vazios, um com cinco litros e outro com três litros de capacidade, todos sem graduação, descobrir a forma de passar quatro litros de água do primeiro para o segundo balde, com o número mínimo de movimentos:
Não gosto de métodos empíricos, pelo que explorei a hipótese de transformar este problema num problema de determinação do caminho mínimo entre dois vértices de um grafo. Um grafo tem vértices e arestas. Os vértices seriam os estados inicial, intermédios e final, e as arestas indicariam ser possível transitar de um para outro estado com um movimento.
Não gosto de métodos empíricos, pelo que explorei a hipótese de transformar este problema num problema de determinação do caminho mínimo entre dois vértices de um grafo. Um grafo tem vértices e arestas. Os vértices seriam os estados inicial, intermédios e final, e as arestas indicariam ser possível transitar de um para outro estado com um movimento.
Primeira questão, de quantas formas será possível distribuir os 8 litros de água pelos três baldes, necessariamente um número inteiro de litros em cada balde. Bem, seria possível usar aqui a regra dos separadores para este cálculo, mas a resposta está à distância de um pequeno programa de computador:
Em cada estado há no máximo 6 movimentos possíveis, do balde 1 para os baldes 2 ou 3, do balde 2 para os baldes 1 ou 3, e do balde 3 para os baldes 1 ou 2, desde que o balde de partida tenha água, e o movimento pode consistir em despejar a água toda ou em encher o balde de destino, não havendo situações intermédias, uma vez que os baldes não têm graduações.
Quantas arestas terá este grafo? Outro pequeno programa de computador ajuda a descobrir que são 106:
e o problema estará resolvido!
O próximo passo é visualizar este grafo (direccionado, digrafo). Utilizei Gephi:
Curiosamente, há 8 vértices inatingíveis (bons para problemas impossíveis...). Retirando-os, e pedindo ao Gephi que mostre, se houver, o caminho mais curto entre os vértices [8, 0, 0] e [4, 4, 0], chegamos a uma solução com comprimento 7 (ramo superior):
Há também uma solução óbvia com comprimento 8 (ramo inferior) e mais um conjunto de soluções de maior comprimento, passando todas pelo vértice [0, 5, 3].
