Você já tentou pagar uma conta em dinheiro e recebeu um troco estranho, cheio de moedas pequenas? Se já passou por isso, talvez tenha pensado: não haveria um modo melhor de dar o troco, com um menor número de moedas?
Embora o uso de cédulas e moedas tenha diminuído com o avanço dos pagamentos digitais, o estudo dos sistemas monetários continua sendo um tema fascinante. A matemática por trás do troco revela conceitos profundos de otimização, que vão muito além das transações do dia a dia e encontram aplicações em diversas áreas do conhecimento.
Uma estratégia bastante natural para obter o "melhor troco" é pegar, sempre que possível, a maior moeda disponível sem ultrapassar o valor desejado. Esse método, conhecido como estratégia gulosa, funciona localmente: a cada passo, escolhemos a opção que parece melhor naquele momento, sem pensar no que vem depois. No sistema monetário brasileiro, por exemplo, se queremos dar 75 centavos, pegamos uma moeda de 50 e uma de 25 — rápido e eficiente.
Mas será que a estratégia gulosa sempre nos dá a melhor solução? Nem sempre! Imagine um sistema de moedas com valores de 1, 3 e 4 centavos. Se precisarmos formar 6 centavos e seguirmos a estratégia gulosa, pegamos a maior moeda disponível, a de 4 centavos. Restam 2 centavos, que só podem ser formados com duas moedas de 1. Total: três moedas. Mas há uma opção melhor: apenas duas moedas de 3 centavos resolveriam o problema!
Isso nos leva a uma pergunta intrigante: o que faz com que alguns sistemas de moedas sempre permitam o uso da estratégia gulosa, enquanto outros não? Para entender melhor, vejamos um exemplo prático. No sistema monetário brasileiro, temos moedas de 1, 5, 10, 25 e 50 centavos, além da de 1 real. Se quisermos formar um valor como 87 centavos, a estratégia gulosa funciona perfeitamente:
Pegamos a maior moeda possível, 50 centavos, restando 37.
Depois, pegamos uma moeda de 25 centavos, restando 12.
Em seguida, uma moeda de 10 centavos, restando 2.
Finalmente, usamos duas moedas de 1 centavo.
No total, usamos 5 moedas, que é a melhor solução possível. Mas como podemos ter certeza de que isso acontece para qualquer valor?
Uma ferramenta poderosa para responder a essa pergunta é a indução matemática. A ideia da indução é semelhante ao efeito dominó: se conseguimos provar que a estratégia funciona para pequenos valores e que, sempre que ela funciona para um número, ela também funciona para o próximo, então conseguimos garantir que a propriedade vale para qualquer valor. No nosso caso, primeiro, verificamos se a estratégia gulosa funciona para os menores valores possíveis. Depois, mostramos que, se ela funciona para um determinado valor, então também funcionará para o próximo.
Vamos aplicar a noção de indução no caso do sistema monetário brasileiro:
Observamos que a estratégia gulosa funciona para os menores valores, como 1, 5 e 10 centavos.
Suponha que ela funcione para qualquer valor até um certo número V, ou seja, o troco ótimo pode ser obtido sempre escolhendo a maior moeda disponível sem ultrapassar V.
Agora consideramos V+1. O algoritmo guloso escolherá a maior moeda possível, digamos M, tal que M≤V+1. O valor restante será V+1−M que, por hipótese de indução, já pode ser resolvido de maneira ótima. Como apenas acrescentamos uma única moeda a essa solução ótima, a quantidade total de moedas usadas para V+1 também será a menor possível.
Como essa lógica pode ser repetida para qualquer valor, concluímos que a estratégia gulosa sempre funcionará para o sistema monetário brasileiro.
Obs.: Se adicionarmos as cédulas ao conjunto de valores disponíveis (2, 5, 10, 20, 50 e 100 reais), a estratégia gulosa continuará funcionando, garantindo o menor número de unidades monetárias necessárias para compor qualquer valor.
Um sistema monetário para o qual a estratégia gulosa sempre funciona é chamado de sistema canônico. A maioria dos sistemas monetários modernos são projetados para serem canônicos, facilitando transações eficientes e minimizando o número de moedas e cédulas necessárias para compor qualquer valor. Isso é feito através de uma escolha cuidadosa das valores, garantindo que qualquer quantia possa ser formada da maneira mais eficiente possível.
A matemática por trás das moedas nos ensina uma lição valiosa: nem sempre a escolha mais óbvia e imediata é a melhor a longo prazo. Na vida e na matemática, às vezes, vale a pena pensar alguns passos à frente antes de dar o troco!
.
Comments