Otimizando a niqueleira II

Tendo já descoberto que uma moeda de dois centavos ajudaria a reduzir a quantidade de moedas em circulação em 20%, resolvi procurar as configurações ótimas para a niqueleira.

Estendi o programa para testar todas as possibilidades de n moedas. Comecei com quatro e fui até seis. A única restrição foi que todos os conjuntos tivessem a moeda de um centavo, para que todos os valores entre 1 e 99 pudessem ser representados.

Se o Banco Central produzisse apenas quatro moedas, a combinção ótima teria as seguintes moedas:

• 1, 3, 11 e 37 ou
• 1, 3, 11 e 38

Essas duas opções requerem apenas 410 moedas para representar todos os valores. Isso já é melhor que o produzido pelas cinco moedas em circulação (50, 25, 10, 5 e 1). Aposto que haveria inúmeras reuniões noite adentro até que o comitê decidisse por 37 ou 38.

Se produzisse 5 moedas, o Banco Central teria mais opções e o comitê nunca ia achar uma solução que agradasse a todos:

• 45, 20, 8, 3 e 1
• 45, 18, 7, 3 e 1
• 44, 20, 8, 3 e 1
• 44, 18, 7, 3 e 1
• 41, 16, 7, 3 e 1
• 40, 16, 7, 3 e 1

Essas seis combinações produzem uma soma agregada de 346 moedas para representar todos os valores entre 1 e 99. Em média, portanto, seriam precisas 3,49 moedas.

Finalmente, a busca da melhor combinação de seis moedas levou quase um dia inteiro. São 67 milhões de combinações. As campeãs, com uma soma agregada de 313 são:

• 65, 29, 13, 5, 2 e 1
• 64, 29, 13, 5, 2 e 1
• 63, 25, 11, 5, 2 e 1
• 62, 25, 11, 5, 2 e 1

Nenhuma combinação de seis moedas, portanto, produz uma média menor que três. Gostei da moeda de 65 centavos, porque com ela só me faltaria uma nota de R$3 para pagar a lotação.