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 10 litros que está totalmente cheio com 10 litros do novo combustível.
  • Há dois recipientes vazios, um de exatamente 7 litros e outro de exatamente 3 litros.
    O enunciado, porém, não diz explicitamente qual é a tarefa que devemos executar (por exemplo: medir exatamente 5 litros? 1 litro? separar em porções específicas?). Como é muito comum neste tipo de problema de cocho (jarras) a pergunta ser “como obter exatamente 5 litros em algum dos recipientes”, eu vou resolver essa versão clássica: obter exatamente 5 litros no recipiente de 10 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 10 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 permanece 10 litros. Vou representar um estado por um triplo (x,y,z) onde:
  • x é a quantidade de litros no recipiente de 10 L,
  • y é a quantidade de litros no recipiente de 7 L,
  • z é a quantidade de litros no recipiente de 3 L.
    No início o estado é (10,0,0).

Passo 3

Conceitos úteis e por que é possível (ou não) obter certas quantidades.
  • Invariância da massa: a soma x+y+z é sempre 10.
  • 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 10, 7 e 3. Calculando os MDCs: \gcd(10,7)=1,\quad \gcd(1,3)=1,logo \gcd(10,7,3)=1.
    Como o MDC é 1, qualquer volume inteiro entre 0 e 10 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 é 1, 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 10 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 5 litros em 10 L.

Passo 4

Estratégia para construir a solução (ideia por trás da sequência que vou usar).
  • Queremos acabar com x=5. Como a soma total é 10, isso significa que os outros dois recipientes juntos devem conter 5 litros ( y+z=5).
  • Um caminho prático é fazer transferências para redistribuir o líquido até atingir y+z=5, e então mover o conteúdo do recipiente de 3 L para o de 10 L para deixar o de 10 L com exatamente 5 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 (x,y,z)). Começamos em (10,0,0).
  1. Verter do recipiente de 10 L para o de 7 L (enche o 7 L):
    • Antes: (10,0,0).
    • Movimento: passa 7 L.
    • Depois: (3,7,0).
  2. Verter do recipiente de 7 L para o de 3 L (enche o 3 L):
    • Antes: (3,7,0).
    • Movimento: passa 3 L do 7 L para o 3 L (o 7 L passa a ter 4 L).
    • Depois: (3,4,3).
  3. Verter do recipiente de 3 L para o de 10 L:
    • Antes: (3,4,3).
    • Movimento: passa 3 L para o 10 L (agora 10 L tem 6 L).
    • Depois: (6,4,0).
  4. Verter do recipiente de 7 L para o de 3 L:
    • Antes: (6,4,0).
    • Movimento: passa 3 L do 7 L para o 3 L (o 7 L fica com 1 L).
    • Depois: (6,1,3).
  5. Verter do recipiente de 3 L para o de 10 L:
    • Antes: (6,1,3).
    • Movimento: passa 3 L para o 10 L (agora 10 L tem 9 L).
    • Depois: (9,1,0).
  6. Verter do recipiente de 7 L para o de 3 L:
    • Antes: (9,1,0).
    • Movimento: passa todo o 1 L do 7 L para o 3 L (enche parcialmente o 3 L).
    • Depois: (9,0,1).
  7. Verter do recipiente de 10 L para o de 7 L:
    • Antes: (9,0,1).
    • Movimento: passa 7 L do 10 L para encher o 7 L.
    • Depois: (2,7,1).
  8. Verter do recipiente de 7 L para o de 3 L:
    • Antes: (2,7,1).
    • Movimento: o 3 L tem 1 L, então o 7 L passa 2 L para o 3 L até enchê-lo; o 7 L fica com 5 L.
    • Depois: (2,5,3).
  9. Verter do recipiente de 3 L para o de 10 L:
    • Antes: (2,5,3).
    • Movimento: passa 3 L para o 10 L. Como o 10 L tinha 2 L, agora passa a ter 5 L.
    • Depois: (5,5,0).
Chegamos ao estado desejado: exatamente 5 litros no recipiente de 10 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 (x,y,z) a cada ação, fica mais fácil ver padrões e evitar ciclos.
  • Para problemas semelhantes, verifique primeiro o \gcd das capacidades: se o \gcd não divide o volume total que você deseja isolar, então é impossível. Aqui \gcd=1, 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 1 L ou 2 L), e então use essas pequenas quantidades para montar o volume desejado. No passo a passo acima vimos como apareceram restos como 1 L e 2 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 (10,0,0) a exatamente 5 litros no recipiente de 10 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:
(10,0,0)\to(3,7,0)\to(3,4,3)\to(6,4,0)\to(6,1,3)\to(9,1,0)\to(9,0,1)\to(2,7,1)\to(2,5,3)\to(5,5,0).
O estado final é (5,5,0), i.e. 5 litros no recipiente de 10 L.

Exercícios relacionados