Nós precisamos de moedas de 18 centavos?

Lendo o Chance News essa semana, artigo 62, vi um link que levava a um post do blog do Freakonimics, com autoria de Steven Levitt. Nesse post, o Levitt cita um amigo seu, Patrick DeJarnette, que fez um estudo sobre a eficiência do conjunto de moedas do sistema monetário americano {1,5,10,25}. Eis o que o Patrick afirma:

Late one night I was curious how efficient the “penny, nickel, dime, quarter” system was, so I wrote a little script to compare all possible 4-coin systems, with the following stipulations:

1. Some combination of coins must reach every integer value in [0,99].

2. Probability of a transaction resulting in value v is uniform from [0,99].

In other words, you start with $10 and no coins. You buy something at the store. Afterward, the chance you have 43 cents in your pocket is equal to the probability that you have 29 or 99 cents in your pocket (in addition to any bills).

Requirement (1) implies the penny is necessary, as you must have a combination of coins that reach value = 1 cent.

With this in mind, the current combination of coins (penny, nickel, dime, quarter) results in an average of 4.70 coins per transaction..

A parte em negrito resume a definição de eficiência de um conjunto de moedas: 

A eficiência de um conjunto é a média de moedas desse conjunto necessárias em uma transação. 

Uma maneira mais palpável de entender isso: suponha que você saia de casa sem moedas e durante o dia compre algumas coisas. A eficiência do conjunto de moedas que o seu país escolheu está relacionada ao número de moedas que você estará carregando quando voltar para casa.

Mais a frente, o Patrick afirma que, enquanto {1,5,10,25} tem eficiência 4.7, os sistemas mais eficientes são {1,3,11,37} e {1,3,11,38}, com 4.1 de moedas por transação. Fazendo aflorar meu lado nerd, resolvi repetir os experimentos do Patrick, com o duplo objetivo de confirmar os resultados dele e tentar achar algo equivalente para o nosso sistema de 5 moedas {1,5,10,25,50}. 

A respeito do primeiro ponto, a conclusão mais espantosa, considerando o sucesso que o Freakonomics faz, foi a de que o Patrick errou - feio! - nas contas. Aqui eu proponho um problema - a ser (talvez) respondido em posts futuros. Mas você deve ignorar o que está entre tracejados se não gosta desse tipo de coisa.

------------------------------------------------------------

Dado um conjunto de moedas e um certo valor a ser atingido com alguma combinação delas, diga qual é o procedimento que acha a combinação que utiliza menos moedas. Exemplo: usando moedas de {1,5,10,25}, tente achar a "melhor" combinação que totaliza 97 centavos.

Depois de pensar um pouco, a gente em geral é capaz de achar o que parece ser uma solução: pegar a moeda maior até não dar mais. Depois, se ainda não basta, fazer o mesmo com a segunda maior e assim por diante. Infelizmente, esse procedimento gera resultados errados várias vezes. Exemplo: {1,5,22,23} e 67 centavos.

------------------------------------------------------------

A essa altura, talvez caiba uma pergunta: por que existe tanta convicção de que o Patrick errou? Bem, por um motivo bastante convincente: verifiquei, com o Excel (ou seja, na raça) que existem conjuntos mais eficientes do que {1,3,11,37}. Assim, não existe a menor dúvida - os resultados do Patrick não estão corretos. Isso não significa, claro, que os meus estejam. Eu até suspeitaria um pouco deles.

E qual é o conjunto de 4 moedas mais eficiente?

A resposta, por acaso, é bem mais interessante. Explico: se de fato o Patrick estivesse correto, nós não poderíamos dizer que os americanos estão perdendo uma grande oportunidade de usar menos moedas. Ora, imagine a delícia que deve ser fazer somas com os números da "falsa" melhor solução: {1,3,11,37}. É claro que com o hábito isso seria bem menos difícil do que parece, mas acho que ainda sim o {1,5,10,25}, por causa do sistema decimal, mesmo que seja menos confortável para o bolso, é bem mais confortável para a mente.

Segundo as continhas que fiz aqui, o conjunto mais eficiente de moedas, com nota 3.89, é {1,5,18,25}. Ok, ele não tem o 10, que é a moeda mais adequada para fazer contas, mas com esse conjunto cada americano carregaria em média quase uma moeda a menos no bolso!

E, finalmente, qual é o conjunto de 5 moedas mais eficiente?

Uau, meu computador demorou mais de 15 minutos para achar a resposta certa. Isso ocorreu porque eu não fui muito esperto na abordagem do problema - minha solução não prestaria para achar conjuntos "ideais" maiores. Enfim, se o pessoal da Casa da Moeda do Brasil quisesse cunhar menos peças, o conjunto de 5 moedas mais adequado seria {1,5,16,23,33}, cuja eficiência é 3.29. Mas esse é um conjunto pouco prático para fazer contas - se determinássemos que só são aceitáveis moedas com valor múltiplo de 5, o melhor conjunto seria {1,5,15,35,45}, com eficiência  4.0, pouco superior à do atual conjunto {1,5,10,25,50}.

A gente pensa que a moeda de 50 merece carinho, porque permite carregar valores altos com poucas moedas, mas na verdade ela atrapalha mais do que ajuda. A razão é simples: a existência da moeda de 50 no lugar de outra menor não permite que a gente carregue valores menores com poucas moedas também.

Aliás, a eficiência do nosso sistema {1,5,10,25,50} é 4.2, muito ruim. Existem conjuntos menores, como {1,5,18,25}, bem mais eficientes.

Enfim: talvez moedas de 18 centavos sejam uma boa...