¿De cuántas maneras distintas podemos dar el cambio de 1 euro?

Este es un clásico y curioso desafío en su versión americana y con dólares como moneda. En Ways to Make Change for a Dollar se da la solución y se descomponen todas las posibles combinaciones de monedas. En total, son 293 maneras distintas de dar cambio de 1 dólar. Esta es una tabla para distintas cantidades a cambiar:

Cantidad de dinero	Maneras de cambiar
1 cents	0
5 cents	1
10 cents	3
25 cents	12
50 cents	49
1 dólar	292

Aclarar que las 293 maneras son posibles si se permite usar una moneda de 1 dólar para realizar el cambio.

El mismo problema se puede trasladar a la zona euro, con la particularidad de que nuestra moneda tiene un abanico de posibilidades más amplia al disponer de un valor más, el de 2 céntimos.

Para realizar el cálculo habría que recurrir a funciones generatrices como la descrita en el capítulo 10 de Lectures on Integer Partitions, o usar pequeños códigos algo menos elegantes. Mediante uno de estos últimos en Perl, el número de maneras distintas de cambiar una moneda de euro serian 4.562 (y espero no haberme equivocado en los cálculos). En este caso no se ha tenido en cuenta la posibilidad de utilizar la moneda de 1 euro para realizar el cambio.

Esta sería una tabla para distintas cantidades en euros:

Cantidad de dinero	Maneras de cambiar
1 cents	0
2 cents	1
5 cents	3
10 cents	10
20 cents	40
50 cents	450
1 euro	4.562

Este reto se puede modificar cambiando el número de monedas a usar, las cantidades a cambiar, etc...

En Making Change se puede descargar una pequeña aplicación que permite realizar los cálculos de forma automática en dólares, y con la posibilidad de encontrar el conjunto más pequeño de monedas con los que no se puede dar cambio a una determinada cantidad, y el conjunto de monedas con el mayor valor mediante el cual no se pueda dar un determinado cambio.

Este último caso es el que ha comenzado toda la entrada a raíz de Changeless: Es posible tener 1,19 dólares (ver distribución de monedas en la entrada original), y no ser capaz de dar cambio para 1 dólar". En Coin puzzles se puede encontrar también este reto, y algunos más bastante graciosos relacionados con monedas.

Otro punto interesante que no me había planteado nunca es el de las máquinas de cambio. No solo deben ser capaces de dar un cambio correcto y rápido, si no que también deben ser capaces de hacerlo de una manera óptima con el fin de no llenar el bolsillo del usuario de monedas que no desea. En este caso, y como se explica en Brother, can you spare some change? (sí, de aquí saque el código en Perl), en este caso se necesita recurrir a un método de programación dinámica y al empleo de algoritmos voraces para encontrar el mínimo número de monedas para dar cambio.

El tema del problema del sello de correos lo dejaremos para otro día.