Questão 1. Para conseguir exatamente 4 litros de combustível (em qualquer vasilhame), qual o número mínimo de vezes o professor deve derramar o conteúdo de um vasilhame para outro?
◯ 1
◯ 2
◯ 3
◯ 4
◯ 5
◯ 1
◯ 2
◯ 3
◯ 4
◯ 5
Passo 1
O enunciado (como foi enviado) diz apenas: “Para conseguir exatamente 4 litros de combustível (em qualquer vasilhame), qual o número mínimo de vezes o professor deve derramar o conteúdo de um vasilhame para outro?” e oferece as alternativas
.
Informações explícitas que o enunciado fornece:
Informações explícitas que o enunciado fornece:
- O objetivo final é obter exatamente
litros (em qualquer vasilhame). - Pergunta sobre o número mínimo de vezes que se deve “derramar o conteúdo de um vasilhame para outro”.
Informações relevantes que NÃO foram fornecidas (ou são ambíguas) e são essenciais para resolver o problema:
- Quantos vasilhames existem? (dois? três? mais?)
- As capacidades de cada vasilhame (por exemplo:
L e L; ou L e L; etc.). - Os volumes iniciais em cada vasilhame (estão vazios? cheio(s)? há abastecimento externo para encher?).
- Quais operações são permitidas e como são contadas: encher de uma fonte infinita, esvaziar no chão, trocar (derramar) parcialmente até um ficar cheio ou o outro vazio, e — muito importante — se a contagem pedida refere-se apenas ao ato de “derramar de um vasilhame para outro” (transferências entre vasilhames) ou se também conta enchimentos/esvaziamentos externos como “ações”.
Sem essas informações a questão é indecidível: diferentes conjuntos de capacidades e regras geram respostas diferentes.
Passo 2
Por que realmente precisamos das capacidades e das regras? Vou explicar didaticamente o porquê, de um jeito prático: essas perguntas são clássicas do tipo “problema das jarras” (water jug problem). A solução depende apenas das capacidades (e das regras permitidas). Há duas partes lógicas para decidir se é possível e, se possível, como encontrar o número mínimo de derramadas.
- Primeira questão: existência — é possível obter exatamente
litros com jarras de capacidades e ? - Segunda questão: otimização — se for possível, qual o mínimo de transferências (derramadas) necessárias, segundo a contagem solicitada?
Vou agora ensinar a teoria usada para responder as duas partes. Assim, quando tiveres as capacidades, vais poder aplicar o método passo a passo.
Passo 3
Teoria de existência (condição necessária e suficiente para dois vasilhames)
- Suponha que temos duas jarras com capacidades
e (inteiras, em litros), e queremos medir exatamente litros, com . - A condição clássica (teorema usando o algoritmo de Euclides / identidade de Bézout) é: existe solução se, e somente se,
ou seja, o máximo divisor comum de
e
divide
. Além disso
não pode ser maior que a maior capacidade disponível:
Explicação curta do porquê (intuitiva): todas as quantidades alcançáveis com operações de encher/esvaziar/derramar entre duas jarras são combinações inteiras de
e
que, em termos de diferença, mudam por múltiplos de
. Bézout garante que existem inteiros
tais que
; multiplicando, obtém-se combinações que permitem chegar a qualquer múltiplo de
.
Passo 4
O que conta como “derramar”? Ambiguidade importante
- Em muitos problemas tradicionais, contam-se todas as ações (encher, esvaziar, derramar). Noutra formulação (como aqui parece pedir: “número de vezes o professor deve derramar o conteúdo de um vasilhame para outro”) pode ser que se queira contar apenas as transferências entre vasilhames (cada vez que se deita o conteúdo de um para outro). É essencial decidir isso antes de contar.
- Vou explicar ambos os pontos de vista; quando tiveres o enunciado completo, escolhe a interpretação correta do problema do teu professor.
Passo 5
Método prático para dois vasilhames — como obter o número (algoritmo padrão)
- Para dois vasilhames com capacidades
e e objetivo (assumindo que a condição de existência acima é satisfeita), há duas estratégias canônicas que produzem a solução com número relativamente pequeno de ações: - Repetidamente encher a jarra de capacidade
e derramar para a jarra até conseguir em alguma jarra. - Repetidamente encher a jarra de capacidade
e derramar para a jarra .
- Repetidamente encher a jarra de capacidade
- Cada uma dessas duas estratégias gera uma sequência de estados (pares de volumes). Conta-se o número de derramadas entre jarras (se essa for a métrica desejada) durante a execução; o mínimo entre as duas estratégias dá o número mínimo de derramadas numa solução “padrão”.
- Procedimento passo a passo (para simular a estratégia “encher
e derramar em ”): - Começar com
. - Enquanto nenhum dos recipientes contiver
: - Se a jarra fonte (capacidade
) estiver vazia, enche-la (operação de enchimento — pode ou não contar). - Derramar da jarra fonte para a jarra destino (capacidade
) até que a fonte fique vazia ou o destino fique cheio. Contar 1 derramamento. - Se o destino ficar cheio, esvaziá-lo (operação de esvaziamento — pode ou não contar).
- Repetir.
- Se a jarra fonte (capacidade
- A outra estratégia é simétrica trocando
e .
- Começar com
- Essa simulação dá um número finito de derramamentos; tomar o mínimo entre as duas estratégias costuma dar o mínimo global quando só se permitem essas operações básicas. Para garantir minimalidade em qualquer variante do problema (mais jarras, contagem diferente), o método geral é modelar o problema como um grafo de estados e aplicar BFS: cada nó é um vetor de volumes; cada aresta é uma derramamento entre dois vasilhames; BFS fornece o menor número de derramamentos necessários para alcançar algum estado com
litros.
Passo 6
Exemplo ilustrativo (sem assumir o teu enunciado)
- Para fixar a ideia, vejamos o clássico exemplo com capacidades
e litros e objetivo litros. Aqui que divide e , portanto é possível. - Seguindo a estratégia "encher
e derramar para ": - Enche
(estado ). - Derrama de
para (1ª derramamento) -> estado . - Esvazia a
(estado ). - Derrama de
para (2ª derramamento) — atenção: aqui a jarra de está vazia, então primeiro enche-se novamente e em seguida derrama; depois do segundo derramamento obtemos . - Temos
litros na jarra de .
- Enche
- Contando apenas derramamentos entre jarras: foram
derramamentos no total (os momentos em que se transferiu de uma jarra para outra). Se também contássemos enchimentos/esvaziamentos como ações, o total seria maior. - Esse exemplo mostra que, dependendo das capacidades, o número mínimo de derramamentos pode ser
(no caso e ). Mas outro par de capacidades poderia dar , , , etc.
Passo 7
Conclusão prática para o enunciado recebido
- Com os dados fornecidos na tua mensagem NÃO É POSSÍVEL determinar um único número mínimo de vezes que o professor deve derramar, porque faltam informações essenciais (capacidades, volumes iniciais e definição precisa do que se conta como “ação”).
- Para resolver concretamente o problema é necessário conhecer pelo menos:
- o número de vasilhames e as capacidades
(em litros); - os volumes iniciais em cada vasilhame (normalmente todos vazios ou algum cheio);
- a convenção de contagem (só derramamentos entre vasilhames, ou também enchimentos/esvaziamentos).
- o número de vasilhames e as capacidades
- Quando esses dados estiverem definidos, aplica-se a condição de existência via
(se forem duas jarras) e então simula-se as duas estratégias ou faz-se um BFS no espaço de estados para obter o número mínimo de derramamentos. Posso fazer isso passo a passo assim que as capacidades e regras estiverem claras.
Resposta
Não é possível determinar um número mínimo com os dados fornecidos — faltam informações essenciais (capacidades dos vasilhames, volumes iniciais e definição precisa de quais operações contam).