1.1.1.7. Novo combustível:
O prof. José é um inventor muito inventivo. Seu último invento é um combustível produzido a partir de bananas. Ele produziu 10 litros do combustível, que estão armazenados em um vasilhame de exatamente 10 litros. Ele tem dois outros vasilhames vazios, de exatamente 7 litros e 3 litros.
Passo 1
O enunciado dá as seguintes informações (tirei estas informações diretamente do enunciado):
- Há um recipiente de exatamente
litros que está totalmente cheio com litros do novo combustível. - Há dois recipientes vazios, um de exatamente
litros e outro de exatamente litros.
O enunciado, porém, não diz explicitamente qual é a tarefa que devemos executar (por exemplo: medir exatamentelitros? litro? separar em porções específicas?). Como é muito comum neste tipo de problema de cocho (jarras) a pergunta ser “como obter exatamente litros em algum dos recipientes”, eu vou resolver essa versão clássica: obter exatamente litros no recipiente de litros, explicando passo a passo e ensinando os conceitos que aparecem. Se a sua pergunta fosse outra, me diga depois e eu faço o passo a passo para esse outro alvo.
Passo 2
Regras de operação (o que é permitido). É importante entender quais ações são possíveis; isso define o “espaço de estados” do problema:
- Pode-se verter de um recipiente para outro até que o recipiente fonte fique vazio ou o recipiente destino fique cheio, o que ocorrer primeiro.
- Pode-se esvaziar um recipiente no ralo (se necessário).
- Pode-se encher um recipiente de alguma fonte (aqui só o recipiente de
L começa cheio; não há fonte de líquido adicional).
Essas operações não criam nem destroem combustível: a quantidade total sempre permanecelitros. Vou representar um estado por um triplo onde: -
é a quantidade de litros no recipiente de L, -
é a quantidade de litros no recipiente de L, -
é a quantidade de litros no recipiente de L.
No início o estado é.
Passo 3
Conceitos úteis e por que é possível (ou não) obter certas quantidades.
- Invariância da massa: a soma
é sempre . - Teorema de alcance por capacidade (forma intuitiva): as quantidades inteiras que é possível obter em qualquer recipiente são múltiplos do máximo divisor comum das capacidades. Aqui as capacidades são
, e . Calculando os MDCs: logo .
Como o MDC é, qualquer volume inteiro entre e litros é teoricamente alcançável (esta é uma consequência de que combinações de transferências permitem efetivamente realizar combinações lineares das capacidades; não vou formalizar toda a prova, mas essa é a ideia e é importante: porque o MDC é , não há uma restrição modular que impeça volumes inteiros). - Estratégia prática: modelar o problema como um grafo de estados e procurar um caminho (busca em largura/BFS) até um estado que tenha o volume desejado no recipiente de
L. Para a prova, normalmente é suficiente saber que, com raciocínio passo a passo, dá para achar a sequência de despejos/vertimentos. Vou mostrar uma sequência explícita para obter litros em L.
Passo 4
Estratégia para construir a solução (ideia por trás da sequência que vou usar).
- Queremos acabar com
. Como a soma total é , isso significa que os outros dois recipientes juntos devem conter litros ( ). - Um caminho prático é fazer transferências para redistribuir o líquido até atingir
, e então mover o conteúdo do recipiente de L para o de L para deixar o de L com exatamente L. - Vou detalhar cada transferência e mostrar o estado resultante; assim você aprende a raciocinar igual na prova.
Passo 5
Sequência de ações passo a passo (cada linha: operação realizada e o novo estado
). Começamos em
.
-
Verter do recipiente de
L para o de L (enche o L): - Antes:
. - Movimento: passa
L. - Depois:
.
- Antes:
-
Verter do recipiente de
L para o de L (enche o L): - Antes:
. - Movimento: passa
L do L para o L (o L passa a ter L). - Depois:
.
- Antes:
-
Verter do recipiente de
L para o de L: - Antes:
. - Movimento: passa
L para o L (agora L tem L). - Depois:
.
- Antes:
-
Verter do recipiente de
L para o de L: - Antes:
. - Movimento: passa
L do L para o L (o L fica com L). - Depois:
.
- Antes:
-
Verter do recipiente de
L para o de L: - Antes:
. - Movimento: passa
L para o L (agora L tem L). - Depois:
.
- Antes:
-
Verter do recipiente de
L para o de L: - Antes:
. - Movimento: passa todo o
L do L para o L (enche parcialmente o L). - Depois:
.
- Antes:
-
Verter do recipiente de
L para o de L: - Antes:
. - Movimento: passa
L do L para encher o L. - Depois:
.
- Antes:
-
Verter do recipiente de
L para o de L: - Antes:
. - Movimento: o
L tem L, então o L passa L para o L até enchê-lo; o L fica com L. - Depois:
.
- Antes:
-
Verter do recipiente de
L para o de L: - Antes:
. - Movimento: passa
L para o L. Como o L tinha L, agora passa a ter L. - Depois:
.
- Antes:
Chegamos ao estado desejado: exatamente
litros no recipiente de
L.
Passo 6
Explicação prática e dicas para a prova (o raciocínio por trás e como generalizar):
- Cada passo é uma aplicação direta da regra “verter até o recipiente fonte ficar vazio ou o recipiente destino encher”.
- Se você desenvolver um hábito de anotar o estado
a cada ação, fica mais fácil ver padrões e evitar ciclos. - Para problemas semelhantes, verifique primeiro o
das capacidades: se o não divide o volume total que você deseja isolar, então é impossível. Aqui , então qualquer volume inteiro é alcançável. - Uma estratégia prática para a prova: procure transformar o problema em conseguir um pequeno “resto” em um dos recipientes (por exemplo
L ou L), e então use essas pequenas quantidades para montar o volume desejado. No passo a passo acima vimos como apareceram restos como L e L que foram úteis. - Se precisar encontrar a sequência mais curta, pense em modelar o problema mentalmente como um grafo e executar uma busca em largura (BFS) — na prova, não é necessário programar, mas raciocinar em camadas “estados a 1 operação, 2 operações, 3 operações …” costuma funcionar.
Resposta
Uma sequência de operações que leva de
a exatamente
litros no recipiente de
L é:
10→7, 7→3, 3→10, 7→3, 3→10, 7→3, 10→7, 7→3, 3→10,
que correspondem aos estados intermediários:
.
O estado final é , i.e.
litros no recipiente de
L.
10→7, 7→3, 3→10, 7→3, 3→10, 7→3, 10→7, 7→3, 3→10,
que correspondem aos estados intermediários:
O estado final é