O Banco Central do Brasil decidiu criar em 2024 uma moeda comemorativa dos seus 60 anos de fundação. O objetivo dessa moeda é facilitar o pagamento de valores de até 1 real em moedas. Atualmente, para pagar alguns valores, é necessário usar um número alto de moedas. Por exemplo, para pagar 19 centavos são necessárias 6 moedas: 19 = 10 + 5 + 1 + 1 + 1 + 1.
Como matemático contratado pelo banco central, o seu papel é de reduzir o número médio de moedas necessárias para representar quantias de 1 centavo a 100 centavos (1 real), supondo todas as quantias equiprováveis.
(a) Qual valor você propõe para uma moeda nova?
(b) E se fossem duas moedas novas?
(c) E se você pudesse parar a circulação das moedas atuais e propor cinco valores novos? Considere que atualmente existem moedas de 1, 5, 10, 25 e 50 centavos e de 1 real (100 centavos).
1 – Qual valor você propõe para uma moeda nova?
Para cada conjunto de moedas, você pode calcular o número mínimo de moedas necessárias para representar cada valor de 1 a 100 usando programação dinâmica. Esse método garante que você encontre a menor quantidade possível de moedas para cada quantia.
A ideia é construir um vetor dp[0…100] onde:
dp[a] é o número mínimo de moedas para formar a centavos.
Inicialmente dp[0] = 0 e os outros começam grandes.
Para cada valor a e cada moeda c, atualizamos: dp[a] = min(dp[a], dp[a – c] + 1)
Ao final, computa-se a média de dp[1] até dp[100]. Quanto menor essa média, melhor o conjunto de moedas.
Situação atual: Moedas: {1, 5, 10, 25, 50, 100}
Média de moedas necessárias para formar 1…100 = aproximadamente 4,21 moedas.
Rodando o programa para testar todas as possíveis moedas novas (entre 2 e 99 não existentes no sistema), encontramos:
O conjunto de moedas com a menor média de moedas seria {1, 5, 10, 25, 50, 100, 18}, tendo uma média de aproximadamente 3.19.
Resposta: Adicionar a moeda de 18 centavos.
2 – E se fossem duas moedas novas?
Agora escolhemos dois novos valores entre 2 99 para complementar as moedas atuais.
O conjunto de moedas com a menor média necessária seria {1, 5, 10, 25, 50, 100, 8, 37}, tendo uma média de aproximadamente 2.81.
Resposta: Adicionar as moedas de 8 e 37 centavos.
3 – E se você pudesse parar a circulação das moedas atuais e propor cinco valores novos?
Aqui permitimos escolher 5 moedas novas do zero (sem assumir as atuais), com uma condição:
• Uma moeda obrigatoriamente de 1 centavo, para poder formar todos os valores
O conjunto de moedas com a menor média necessária seria {1, 5, 16, 23, 33}, tendo uma média de aproximadamente 3.33.
Resposta: As moedas seriam as de 1, 5, 16, 23 e 33 centavos.
Código para a solução
import itertools
def avg_mincoins(denoms, max_amount=100):
denoms = sorted(set(denoms))
INF = 10**9
dp = [INF] * (max_amount + 1)
dp[0] = 0
for a in range(1, max_amount + 1):
dp[a] = min(dp[a - c] + 1 for c in denoms if c <= a)
return sum(dp[1:]) / max_amount
base = [1, 5, 10, 25, 50, 100]
# (a) +1 moeda
best_a = None
for x in range(1, 100):
avg = avg_mincoins(base + [x])
if best_a is None or avg < best_a[0]:
best_a = (avg, x)
# (b) +2 moedas novas
cand = [i for i in range(1, 100) if i not in base]
best_b = None
for x, y in itertools.combinations(cand, 2):
avg = avg_mincoins(base + [x, y])
if best_b is None or avg < best_b[0]:
best_b = (avg, (x, y))
# (c) 5 novas do zero
best_c = None
ties = []
for a, b, c, d in itertools.combinations(range(2, 101), 4):
avg = avg_mincoins([1, a, b, c, d])
if best_c is None or avg < best_c[0]:
best_c = (avg, (1,a,b,c,d))
ties = [best_c[1]]
elif abs(avg - best_c[0]) < 1e-12:
ties.append((1,a,b,c,d))
Solução de Eduardo Cabrera (Giant Steps)